DEV Community: Fabian Quijosaca

Mandelbrot Set in JS - Smooth Scroll Zoom & Fixing Floating-Point Precision

Fabian Quijosaca — Mon, 06 Apr 2026 18:33:12 +0000

This is a follow-up to Mandelbrot Set in JS - Zoom In.
In that article we built a Mandelbrot renderer using Canvas and Web Workers, with click-to-zoom.
This post covers what broke after ~16 zooms, why it broke (floating-point precision),
and how we replaced click zoom with a smooth scroll-based zoom that also lets you zoom back out.

The Problem: Everything Turns Black After ~16 Clicks

If you played with the previous demo long enough, you noticed something strange: after zooming in about 16 times, the fractal starts looking pixelated, blocky, and eventually the entire canvas turns solid black.

This isn't a bug in the Mandelbrot math. The set is infinitely detailed, there's always more structure to see. The problem is in how computers store decimal numbers.

Root Cause: JavaScript Numbers Have Limited Precision

JavaScript (like most languages) stores all numbers as 64-bit IEEE 754 doubles. This is just the standard format computers use for decimal numbers, and it gives you about 15 to 17 significant digits of precision. That sounds like a lot, but zoom burns through those digits very fast.

How the old zoom worked

Each click zoomed to a window of 2 × ZOOM_FACTOR × canvas_width pixels centered on the click point. With ZOOM_FACTOR = 0.1, each zoom reduced the visible range to 20% of the previous range:

const zfw = WIDTH * ZOOM_FACTOR;  // 800 * 0.1 = 80px on each side
REAL_SET = {
  start: getRelativePoint(e.pageX - canvas.offsetLeft - zfw, WIDTH, REAL_SET),
  end:   getRelativePoint(e.pageX - canvas.offsetLeft + zfw, WIDTH, REAL_SET),
};

The coordinate range after N clicks shrinks like this:

range_after_N = initial_range × 0.2^N

Clicks	Real axis range
0	3.0 (from -2 to 1)
5	~0.00077
10	~2.4 × 10⁻⁷
15	~7.5 × 10⁻¹²
16	~1.5 × 10⁻¹²

At click 15, the range is 7.5e-12. If your center is around -0.7, the coordinates look like:

start: -0.700000000003750
end:   -0.700000000003751

Those two numbers share 15 digits. With only 15 to 17 digits of total precision, the difference between adjacent pixels becomes too small to represent. Every pixel ends up mapping to the same value. Result: a grid of identical colors, pixelation, black.

This is called catastrophic cancellation: when you subtract two numbers that are almost the same, you lose all the useful digits.

The Fix, Part 1: Replace Click with Scroll Zoom

The first change is switching from click to wheel (scroll). This gives us:

Zoom in (scroll up) and zoom out (scroll down) with the same gesture
Smooth, step-by-step control over the zoom level
The zoom always centers on the cursor position

Here is the complete new listener:

const ZOOM_FACTOR = 0.8; // each scroll step = 80% of current range (zoom in)
const MIN_RANGE = 1e-12; // safety limit, stop before precision breaks down

const startListeners = () => {
  canvas.addEventListener('wheel', (e) => {
    e.preventDefault();
    const zoomIn = e.deltaY < 0;
    const factor = zoomIn ? ZOOM_FACTOR : 1 / ZOOM_FACTOR;

    const realRange = REAL_SET.end - REAL_SET.start;
    const imagRange = IMAGINARY_SET.end - IMAGINARY_SET.start;
    const newRealRange = realRange * factor;
    const newImagRange = imagRange * factor;

    // Stop zooming in before precision collapses
    if (newRealRange < MIN_RANGE || newImagRange < MIN_RANGE) return;

    // Map cursor pixel to a point in the complex plane
    const mouseX = e.pageX - canvas.offsetLeft;
    const mouseY = e.pageY - canvas.offsetTop;
    const centerReal = getRelativePoint(mouseX, WIDTH, REAL_SET);
    const centerImag = getRelativePoint(mouseY, HEIGHT, IMAGINARY_SET);

    REAL_SET = {
      start: centerReal - newRealRange / 2,
      end:   centerReal + newRealRange / 2,
    };
    IMAGINARY_SET = {
      start: centerImag - newImagRange / 2,
      end:   centerImag + newImagRange / 2,
    };

    Mandelbrot();
  }, { passive: false }); // passive: false is required to call e.preventDefault()
};

Let's go through each decision:

`e.preventDefault()` + `{ passive: false }`

By default, browsers treat wheel events as passive for performance, assuming you won't stop the default scroll behavior. We need to prevent the page from scrolling while the user zooms the fractal, so we have to opt out. Without { passive: false }, calling preventDefault() does nothing and the page scrolls anyway.

`factor = zoomIn ? ZOOM_FACTOR : 1 / ZOOM_FACTOR`

Zooming in multiplies the range by 0.8 (makes it smaller). Zooming out divides by 0.8 (makes it bigger). This keeps zoom in and out symmetric, so ten zooms in followed by ten zooms out brings you back to exactly where you started.

Centering on the cursor

The new approach maps the cursor pixel to a point in the complex plane, then builds the new window symmetrically around it:

const centerReal = getRelativePoint(mouseX, WIDTH, REAL_SET);
const centerImag = getRelativePoint(mouseY, HEIGHT, IMAGINARY_SET);

getRelativePoint converts a pixel position to a coordinate using a simple formula:

const getRelativePoint = (pixel, length, set) =>
  set.start + (pixel / length) * (set.end - set.start);

`ZOOM_FACTOR = 0.8` instead of `0.1`

With 0.1, each click zoomed to 20% of the range, which was very aggressive. The precision limit was hit in 16 steps. With 0.8, each scroll step reduces the range by only 20%, so you can zoom about 130 times before hitting the same limit. It also feels much smoother to use.

The Fix, Part 2: The Precision Guard

if (newRealRange < MIN_RANGE || newImagRange < MIN_RANGE) return;

With MIN_RANGE = 1e-12 we stop zooming in when the coordinate window gets too small. At that scale, the numbers don't have enough precision left to render a meaningful image. Instead of turning black, the fractal just stays frozen at the last good zoom level. The scroll event is silently ignored.

How the Renderer Still Works

For context, here is how each column of pixels is computed in the Web Worker. This part is the same as in the previous article:

// worker.ts, runs in a separate thread via Vite's ?worker import

const MAX_ITERATION = 1000;

function mandelbrot(c: { x: number; y: number }): [number, boolean] {
  let z = { x: 0, y: 0 };
  let n = 0;
  let d = 0;
  do {
    const p = {
      x: Math.pow(z.x, 2) - Math.pow(z.y, 2),
      y: 2 * z.x * z.y,
    };
    z = { x: p.x + c.x, y: p.y + c.y };
    d = 0.5 * (Math.pow(z.x, 2) + Math.pow(z.y, 2));
    n += 1;
  } while (d <= 2 && n < MAX_ITERATION);
  return [n, d <= 2];
}

This is the core iteration: z → z² + c. A point c is in the Mandelbrot set if |z| never escapes 2 after MAX_ITERATION steps. Points that do escape get colored by how fast they did it (the value of n).

The main thread sends one message per column and the worker replies with the results:

// columns are dispatched in random order for a cool reveal effect
const launchTasks = () => {
  while (TASKS.length > 0) {
    const [col] = TASKS.splice(Math.floor(Math.random() * TASKS.length), 1);
    worker.postMessage({ col });
  }
};

Current Limitations

Here is an honest list of what this implementation still can't do:

Limitation	Why it happens
~130 scroll steps max zoom	JavaScript number precision (15-17 digits). You need a different approach to go deeper.
Re-renders the full canvas on every scroll event	The worker is restarted on each zoom. Fast scrolling queues many full renders.
No mobile support	`wheel` events don't fire on touch screens. You'd need to handle pinch gestures separately.
Single worker for all columns	One worker handles all 800 columns. Multiple workers could be faster.
Fixed `MAX_ITERATION = 1000`	Deep zoom areas need more iterations to look good, but raising this constant slows everything down.

Future Improvements

1. Arbitrary Precision with `decimal.js`

To zoom beyond ~130 steps you need more than the standard 64-bit number format. The decimal.js library lets you set how many digits of precision you want:

import Decimal from 'decimal.js';

Decimal.set({ precision: 50 }); // 50 significant digits

const newRange = new Decimal(realRange).mul(factor);
const center  = new Decimal(realSet.start)
  .plus(new Decimal(mouseX).div(WIDTH).mul(new Decimal(realSet.end).minus(realSet.start)));

The downside is that this kind of math is 10 to 100 times slower than normal numbers, so you would need to lower the canvas resolution or the number of iterations to keep things running at a good speed.

2. Perturbation Theory

This is the technique used by professional deep-zoom renderers like Kalles Fraktaler. The idea is to compute one very precise reference point and then calculate all other pixels as small adjustments relative to that point, using regular numbers. This can reach zoom depths of 10^1000 and beyond, with good performance, but it requires a solid math background to implement.

3. Adaptive `MAX_ITERATION`

Instead of a fixed limit, scale the number of iterations based on how deep the zoom is, so shallow views are fast and deep views show more detail:

const maxIter = Math.floor(100 + zoomLevel * 50);

4. RAF Throttle

The scroll event fires much faster than the renderer can keep up. Using requestAnimationFrame would skip frames that come in too quickly and only render when the browser is ready:

let rafId: number;
canvas.addEventListener('wheel', (e) => {
  e.preventDefault();
  updateCoordinates(e);
  cancelAnimationFrame(rafId);
  rafId = requestAnimationFrame(() => Mandelbrot());
}, { passive: false });

5. Pinch-to-Zoom (Mobile)

Handle touchstart and touchmove with two fingers to calculate a scale factor and apply the same zoom logic.

Summary of Changes

What changed	Before	After
Interaction	`click`, zoom in only	`wheel`, zoom in and out
Zoom center	Approximate click pixel	Exact cursor coordinate
Zoom step	20% of range per click	20% of range per scroll tick
Precision guard	None, canvas turns black	Stops at `1e-12` range
Max useful zooms	~16	~130
Page scroll behavior	Not a concern	Blocked with `passive: false`

Try It Live

You can see the demo running on quijosakaf.com and find the full source on GitHub.

Repository:
github

If you want to experiment, try changing ZOOM_FACTOR between 0.5 (aggressive) and 0.95 (very smooth). The math works the same either way, it's just a personal preference.

Thanks for Reading

If you made it this far, thank you so much. This kind of topic can get complicated fast, and I appreciate you sticking with it.

I want to be honest: this post was written with the help of AI (Claude). Concepts like IEEE 754, catastrophic cancellation, arbitrary precision arithmetic, and perturbation theory were things I did not know about before I started digging into why the zoom was breaking. The AI helped me understand why each thing was happening and gave me the right words to describe it, which made it much easier to explain here.

The demo will keep improving. The improvements listed above (RAF throttling, adaptive iterations, arbitrary precision, pinch-to-zoom) are real next steps I plan to work on. If you have ideas, found a bug, or just want to talk about fractals, drop a comment below.

Fixing Bluetooth in Debian 9

Fabian Quijosaca — Sat, 08 May 2021 21:00:38 +0000

Some time ago I bought a Lenovo Thinkpad E580 computer, then I decided to install GNU/Linux as my operating system, I chose Debian Wheezy but unfortunately my wifi and bluetooth did not work.

After searching the internet I found a controller that was compatible with my wifi, however I couldn't fix the bluetooth. Back then it wasn't a major problem so I gave up!.

Two months ago I bought a wireless headphone, which works via bluetooth, so this time I decided to fix it.

I followed many instructions that I found on the internet, but still couldn't fix it, then I realized that my computer was showing various messages when it started and in general it was:

bluetooth hci0: firmware: failed to load rtl_bt/*****_config.b
bluetooth hci0: firmware: failed to load rtl_bt/*****_config.bin
bluetooth hci0: firmware: failed to load rtl_bt/*****_fw.bin
...

The problem was obvious, the operating system could not find the bluetooth driver, in the path /lib/firmware/rtl_bt/.

Searching on the internet I found a repository with many different drivers available already compiled (ready to download and use),
So I followed the following instructions to fix it:

Steps to install bluetooth driver

Clone the repository

╰─$ cd /home/user/Downloads/
╰─$ git clone https://github.com/wkennington/linux-firmware.git

If you do not have git installed, here you have the instructions.

Copy bluetooth driver to OS firmware path.

╰─$ sudo cp -R /home/user/Downloads/linux-firmware/rtl_bt/ /lib/firmware

Reboot your pc

╰─$ sudo reboot

Bluetooth fixed!

In my situation, the above steps helped me to finally fix bluetooth on debian wheezy. Then warning messages no longer appeared.

If these steps worked for you, you will see something like this in your bluetooth settings panel (I am using GNOME desktop environment).

Wrapping Up

You just need to download the bluetooth driver and add it to the correct path in your operating system, and reboot.

Remember this is my solution, maybe it is not the correct way to install a driver (due to security issues), but I just wanted to listen to music with my headphones, so for me it was not a big deal, but maybe for you are.

Let me know if this worked for you in the comments.

Thank you for reading my blog post.
Fabian

How to wait for 2 actions to dispatch another? - Redux Saga

Fabian Quijosaca — Fri, 12 Mar 2021 00:39:01 +0000

In some situations, you may want to dispatch an action only after 2 actions have been dispatched in redux-saga, next I will explain step by step how to get this.

First, I will explain the scenario:

Imagine that we have a component called Counter, and it has a button to multiply a value.
A value should be multiplied only when action A followed by action B has been dispatched in order.
If the aforementioned in the previous point is not fulfilled, the action C (multiply action) is not dispatched.

The Counter component has the next signature.



//Counter.js
const Counter = ({ value, initialAction, multiply }) => (
  <div>
    Current Value: {value} times{" "}
    <button onClick={initialAction}>Action A</button>{" "}
    <button onClick={multiply}>Action B</button>
  </div>
);

Counter, has 2 buttons, the first one will be used to dispatch an initial action to process into a saga, then it will dispatch the FIRST ACTION, as shown in the following code.



//sagas.js
import { put, takeLatest, take } from "redux-saga/effects";

export function* initialSaga() {
  // side-effects (http calls)...
  yield put({ type: "FIRST_ACTION" });
}

export function* multiply() {
  // do other things...
  yield take(["SECOND_ACTION"]);
  yield put({ type: "MULTIPLY" });
}

export default function* rootSaga() {
  yield takeLatest("INITIAL_ACTION", initialSaga);
  yield takeLatest("FIRST_ACTION", multiply);
}

The magic occurs in multiply generator function, because it will wait until SECOND_ACTION is dispatched to continue and dispatch a MULTIPLY action.



 yield take(["SECOND_ACTION"]);
 yield put({ type: "MULTIPLY" });

So, when second button (multiply) is clicked, SECOND_ACTION action will be dispatched and multiply generator will continue from the line where it ended previously.

Graphically follow the following order.

By the way, the multiplication is done inside a reducer.



//reducer.js
export default function counter(state = 1, action) {
  switch (action.type) {
    case "MULTIPLY":
      return state * 2;
    default:
      return state;
  }
}

In summary, a value will be multiplied only when 2 actions have been previously executed.

Below you have a complete example.

Redux-Saga is fun and very easy to use, and I love it for that.

Thank you for reading my blog post.
Fabian

The shortest path - BFS

Fabian Quijosaca — Thu, 24 Sep 2020 02:52:09 +0000

In a previous blog, I talked about 2 types of search algorithms, for the tree data structure, which were, the Depth First Search - DFS and Breath First Search DFS, and I mentioned that the The most efficient algorithm to find the shortest path is BFS, this algorithm starts from the root and goes through each node by levels instead of branches as DFS does, using a queue to temporarily store the nodes. On the other hand, with the DFS algorithm, one must go completely branch by branch, so it would be necessary to store each solution found and at the end obtain the solution that has the shortest path.

The problem

There is a list of words and that given the start and end word, the shortest path must be found, starting from the beginning to the end, the only 2 rules are, while looking for the shortest path, only one letter it can be changed at the same time and the intermediate words that are generated must exist in the word list.

Note: This blog is a JavaScript version of JavaByPatel blog.

A simple example is shown below:
start word = CAT
final palatra = DOG
list = CAT, BAT, COT, COG, COW, RAT, BUT, CUT, DOG, WEB

A path could be the following, CAT - RAT - BAT - BUT - CUT - COT - COG - DOG, however the shortest path is, CAT - COT - COG - DOG, BFS algorithm allows go through the shortest path, below is the implementation of this algorithm with its respective explanation.

First, to determine that in a word, only one letter has been changed at a time, the following function is implemented.

function differByOne(word, target) {
    if (word.length !== target.length) return false
    let diffCount = 0

    for (let i = 0; i < word.length; i++) {
        if (target.charAt(i) !== word.charAt(i))
            diffCount++
    }

    return diffCount === 1
}

Next, BFS is implemented, to find the shortest path.

function checkWords(words, start, target) {
    if (!words.has(start) || !words.has(target)) return null

    const queue = []
    const path = []

    path.push(start)
    queue.push(path)
    words.delete(start)

    while (queue.length) {
        const lastPath = queue.shift()
        const lastWord = lastPath[lastPath.length - 1]

        if (target == lastWord) return lastPath

        for (let item of words) {
            if (differByOne(item, lastWord)) {
                const newPath = [...lastPath]
                newPath.push(item)
                queue.push(newtPath)
                words.delete(item)
            }
         }
    }

    return null
}

The checkWords function receives 3 parameters, the first is the list of words which is a data type Set, the start and target word.
Check if the word list does NOT contain the initial or target word, to immediately return null, (!Words.has(start) ||! Words.has(target)).
Declare an array, which will be used as a queue to store the shortest path.
Declare an array called path, to store the selected words.
Add to the path, the start word, path.push(start).
Add the new path to the queue.
Removes the first selected word words.delete(start) from the word list.
As long as there is data in the queue, while (queue.length), the following is done.
Removes the first path (word list) from the queue and returns it, to the lastPath constant.
The last selected word is obtained from the word list obtained in the previous step, const lastWord = lastPath [lastPath.length - 1].
If the last selected word is the final word that is being searched, it returns the list of words obtained (shortest path) if(target == lastWord) return lastPath, in case it is not fulfilled, continue with the following instructions.
The following is done for every word in the word list.
Verify that the current word (item) in the word list only has a different letter with respect to the last selected word (lastWord), differByOne(item, lastWord).
In case the previous condition is met, create a new list (new path) with the words of the last path found (list of words - lastPath) const newPath = [... lastPath].
To the new path, the word that meets the condition explained in previous item, newPath.push(item), is added.
The new path is added to the queue, queue.push(newtPath).
Delete the selected word from the word list, words.delete(item).
In case the final word is not found during the repetitive cycle, null is returned.

Done!, it's time to test the functionality of the algorithm explained above, as shown below.

const words = new Set(['BUT', 'CUT', 'RAT', 'BAT', 'WEB', 'CAT', 'COT', 'COG', 'COW', 'DOG'])
const start = 'CAT'
const target = 'DOG'

console.log(checkWords(words, start, target))

// output
// ["CAT", "COT", "COG", "DOG"]

The previous code calls the checkWords function, the list of words is sent in a data structure of type Set, the initial and target words to be searched, the result is printed in the console. The result will be the shortest path found from the starting word to the end.

The source code is on GitHub.

Was it useful? Show your support and share it.

Stay safe and thank you so much for reading!

Uploading Images to AWS S3 with Serverless

Fabian Quijosaca — Thu, 24 Sep 2020 02:23:17 +0000

AWS S3 is one of the many services provided by Amazon Web Services (AWS), which allows you to store files, most of you probably already know. On the other hand, AWS Lambda is one of the most revolutionary services of our day, although the name may sound very intimidating, AWS Lambda is a computing platform that autonomously manages the computing resources required by the developed code and can execute code to any type of application or back-end service, the purpose of this service is to simplify the creation of applications, because it is not necessary to provision or manage servers, since AWS Lambda also takes care of everything necessary to run and scale your code with high availability, in addition you pay on demand, that is, for the processing time involved in executing the code.

The purpose of this post is to explain how to develop a back-end service, without a server serverless, to upload images (original and thumbnail), using the framework called serverless by the way was developed by the Coca Cola company, for the purpose of creating serverless applications even faster; according to Wikipedia:

Serverless Framework is a free, open source web framework written with Node.js. Serverless is the first framework developed to build applications on AWS Lambda, a serverless computing platform provided by Amazon as part of Amazon Web Services.

In the next few steps, I'll walk you through building a serveless based application, allowing image processing and uploading, on AWS S3, if you'd rather go straight to the code, here it is.

Note (updated): When using AWS Lambda to upload large files to S3, there are a certain limitations of Api Gateway and Lambdas to consider:

Memory: Lambda functions are limited by the amount of memory they are allocated, and this can impact the size of the files that can be uploaded.

Timeout: Lambda functions have a maximum execution time of 15 minutes. (You may need to increase the timeout limit to upload large files)

Payload size: Lambda functions have a payload size limit of 6MB for synchronous invocations and 256KB for asynchronous invocations. (You may need to use an S3 multipart upload to split the file into smaller parts to upload large files)

Network bandwidth: If the Lambda function is located in a region that is far from the S3 bucket, the upload speed may be slower.

Required Tools

Node JS 12
Serverless
AWS CLI

1. Install AWS CLI (Command Line Interface)

AWS CLI, is a unified tool for managing AWS services, it is a tool that allows you to control multiple AWS services from the command line. Once downloaded, add your profile with your respective AWS account and credential.

2. Install the serverless framework

Here is a link that explains this process in detail, https://serverless.com/framework/docs/getting-started/.

3. Run the following command to generate sample code with serverless.

First you need to create a folder, example: serveless-upload-image.

sls create --template hello-world

The above command will create the following files:

serverless.yml
handler.js

In the serverless.yml file, you will find all the information for the resources required by the developed code, for example the infrastructure provider to be used such as AWS, Google Cloud or Azure, the database to be used, the functions to be displayed, the events to be heard, the permissions to access each of the resources, among other things.

The handle.js file contains the generated hello-world code, which is a simple function that returns a JSON document with status 200 and a message. We will rename this file to fileUploaderHome.js.

4. Install dependencies

npm init -y
npm install busboy && uuid && jimp && aws-sdk

Since handling files is required, the client will send a POST request, encoding the body in multipart/form-data format, to decode that format, for which we will use the busboy library. In addition, it is necessary to make a thumbnail of the images, Jimp will be installed, also the library called uuid, to generate a unique identifier for the images, finally, the AWS SDK provides JavaScript objects to manage AWS services, such as Amazon S3, Amazon EC2, DynamoDB among others.

5. Create the function to decode the multipart/form-data

//formParser.js
const Busboy = require('busboy');

module.exports.parser = (event, fileZise) =>
    new Promise((resolve, reject) => {
    const busboy = new Busboy({
        headers: {
            'content-type':
            event.headers['content-type'] || event.headers['Content-Type']
        },
        limits: {
            fileZise
        }
    });

    const result = {
        files: []
    };

    busboy.on('file', (fieldname, file, filename, encoding, mimetype) => {
        const uploadFile = {}
        file.on('data', data => {
            uploadFile.content = data
        });
        file.on('end', () => {
            if (uploadFile.content) {
                uploadFile.filename = filename
                uploadFile.contentType = mimetype
                uploadFile.encoding = encoding
                uploadFile.fieldname = fieldname
                result.files.push(uploadFile)
             }
        })
    })

    busboy.on('field', (fieldname, value) => {
        result[fieldname] = value
    });

    busboy.on('error', error => {
        reject(error)
    })

    busboy.on('finish', () => {
        resolve(result);
    })

    busboy.write(event.body, event.isBase64Encoded ? 'base64' : 'binary')
    busboy.end()
 })

6. Function that will process and upload the images to S3

Below is the step-by-step code that will allow to process the original image and thumbnail to be uploaded to S3.

//fileUploaderHome.js
"use strict";
const AWS = require("aws-sdk")
const uuid = require("uuid/v4")
const Jimp = require("jimp")
const s3 = new AWS.S3()
const formParser = require("./formParser")

const bucket = process.env.Bucket
const MAX_SIZE = 4000000 // 4MB
const PNG_MIME_TYPE = "image/png"
const JPEG_MIME_TYPE = "image/jpeg"
const JPG_MIME_TYPE = "image/jpg"
const MIME_TYPES = [PNG_MIME_TYPE, JPEG_MIME_TYPE, JPG_MIME_TYPE]

module.exports.handler = async event => {
    try {
        const formData = await formParser.parser(event, MAX_SIZE)
        const file = formData.files[0]

        if (!isAllowedFile(file.content.byteLength, file.contentType))
            getErrorMessage("File size or type not allowed")

        const uid = uuid()
        const originalKey = `${uid}_original_${file.filename}`
        const thumbnailKey = `${uid}_thumbnail_${file.filename}`

        const fileResizedBuffer = await resize( file.content, file.contentType, 460)
        const [originalFile, thumbnailFile] = await Promise.all([
            uploadToS3(bucket, originalKey, file.content, file.contentType),
            uploadToS3(bucket, thumbnailKey, fileResizedBuffer, file.contentType)
        ])

        const signedOriginalUrl = s3.getSignedUrl("getObject", { Bucket: originalFile.Bucket, Key: originalKey, Expires: 60000 })
        const signedThumbnailUrl = s3.getSignedUrl("getObject", { Bucket: thumbnailFile.Bucket, Key: thumbnailKey, Expires: 60000 })

        return {
            statusCode: 200,
            body: JSON.stringify({
                id: uid,
                mimeType: file.contentType,
                originalKey: originalFile.key,
                thumbnailKey: thumbnailFile.key,
                bucket: originalFile.Bucket,
                fileName: file.filename,
                originalUrl: signedOriginalUrl,
                thumbnailUrl: signedThumbnailUrl,
                originalSize: file.content.byteLength
             })
          }
    } catch (e) {
        return getErrorMessage(e.message)
    }
}

The resize function (file.content, file.contentType, 460), will be explained in detail later, however in this line a thumbnail image is generated from the original image, with a width of 460 px, and a height determined automatically, this function receives the binary content of the original file, the type of the file and the size at which the thumbnail image will be generated. The await keyword will wait for the image resizing to finish processing to continue to the next line.
The uploadToS3 function receives 3 parameters, the bucket to which it will be uploaded, the key (key) of the file, the content in binary and the file type, and returns a promise, later on what this function does will be explained in detail.
Once we have original and the thumbnail file, it is uploaded to S3, in parallel with Promise.all(...), when it finishes uploading all files it returns an array with the information of each file that has been uploaded. Then the signed url *(getSignedUrl)** is obtained, with a specified expiration time, using the AWS S3 client.
This function, finally in case everything is executed successfully, returns a JSON, with the information of the processed images.

In the following block, each one of the utilitarian functions used from the previous code block is detailed.

const getErrorMessage = message => ({ statusCode: 500, body: JSON.stringify( message })})

const isAllowedFile = (size, mimeType) => { // some validation code }

const uploadToS3 = (bucket, key, buffer, mimeType) =>
    new Promise((resolve, reject) => {
        s3.upload(
            { Bucket: bucket, Key: key, Body: buffer, ContentType: mimeType },
            function(err, data) {
                if (err) reject(err);
                resolve(data)
            })
    })

const resize = (buffer, mimeType, width) =>
    new Promise((resolve, reject) => {
        Jimp.read(buffer)
        .then(image => image.resize(width, Jimp.AUTO).quality(70).getBufferAsync(mimeType))
        .then(resizedBuffer => resolve(resizedBuffer))
        .catch(error => reject(error))
    })

Well, so far we have reviewed each of the code blocks that allow image processing, validation and uploading to S3, however, the control file serverless.yml of the serverless framework needs to be covered, which allows us to detail the resources , service definitions, roles, settings, permissions, and more for our service.

#serverles.yml
service: file-UploaderService-foqc-home
custom:
    bucket: lambda-test-foqc-file-home
provider:
    name: aws
    runtime: nodejs12.x
    region: us-east-1
    stackName: fileUploaderHome
    apiGateway:
        binaryMediaTypes:
            - '*/*'
    iamRoleStatements:
        - Effect: "Allow"
        Action:
            - "s3:PutObject"
            - "s3:GetObject"
        Resource:
            - "arn:aws:s3:::${self:custom.bucket}/*"
functions:
    UploadFileHome:
        handler: fileUploaderHome.handler
        events:
            - http:
                path: upload
                method: post
                cors: true
        environment: Bucket: ${self:custom.bucket}
resources:
    Resources:
        StorageBucket:
            Type: "AWS::S3::Bucket"
            Properties:
                BucketName: ${self:custom.bucket}

service, refers to a project, is the name with which it will be deployed.
custom, this section allows defining variables that can be used at various points in the document, centralizing the values for development or deployment, therefore we add the bucket variable, with the value lambda-test-foqc-file-home, this value will be used to define the bucket in which the files will be stored.
Provider, in this section the provider, the infrastructure and the respective permissions of resources is defined. As mentioned at the beginning of this blog, the provider to use is Amazon Web Services (aws), NodeJs 12, region in which it will be deployed is in the eastern United States, the default name of the CloudFormation stack (fileUploaderHome), however it is not required.
The following line is important, to allow our Api Gateway support binary files; It is mandatory to declare the section apiGateway which has as one of its values '* / *', which is a wildcard that defines, that any binary format, such as multipart/form-data, will be accepted. Then the permissions (iamRoleStatements) are defined, to allow access to S3 bucket, defined in the customization section ${self.custom.bucket}.
Functions, this section defines each of the implementations of functions as services (Faas), it is a minimum unit of deployment, a service can be composed of several functions, and each of these must fulfill a single task, although it is just a recommendation. Each function must have a specific configuration, otherwise it will inherit one by default.
The name of our function will be the following, UploadFileHome, which is invoked from an HTTP POST event in the path that is fired on demand and allows CORS, this event will be handled by our handler function that has already been implemented in the file *fileUploaderHome.
Resources, finally in this section the resources to be used by each of the functions, defined above, are defined. The storage bucket (StorageBucket) is defined, which has the type (Type: 'AWS :: S3 :: Bucket') and in the property the name of the bucket (BucketName).

Finally! We have finished building our service, which uploads an image and its thumbnail to S3, so it is time to deploy the service, with the following command.

sls deploy --stage=test

At the end of the deployment, the url of our service will be displayed, test its operation using postman, as shown in the image.

If the image uploading was successful, the service will return a JSON, with the information of the processed image, such as the key, the name, the url of the original file and the thumbnail.

To conclude, in case you need to remove the service, run the following command.

sls remove --stage=test

Conclusions

This service can be used on demand by any external application or service, since it is not coupled to any business logic, in addition the code can be refactored so it can upload files in general, not only images, it could also receive as part of the http post event, the directory (path) of the bucket where you want to store the file, avoiding having a fixed directory. However, in a didactic way, it serves as a basis for creating a more robust and configurable service.

It has taken me several days to document and write this post, I am satisfied and I hope that this information has been useful for you.

Thank you!

Plotting a binary tree in JavaScript

Fabian Quijosaca — Thu, 24 Sep 2020 01:23:54 +0000

A tree in computer science is a data structure that has a wide use in the field of computer science, it has a root, a sub-tree of children with a parent node, represented as a set of linked nodes. This data structure has extensive use cases, trees are the basis of other data structures such as Maps and Sets, in addition to a clear example of the use of trees are fast searches in databases and representing the HTML DOM hierarchy. There are different types of trees, however in this post we will implement and graph a binary tree using Canvas and JavaScript.

What is a binary tree?

A binary tree is a data structure, it begins with a top node called root and branches with its descendants (sub-trees) until it finally ends at nodes called leaves. Each node can have a maximum of 2 children, left and right. In case that node does not have any reference, it means it does not have children, it is called leaves or external node.

Implementing the binary tree data structure

In the previous blog you realized that a binary tree is a data structure, where each node has a value and pointers (links) to 2 children or descendants, below is the implementation of a node.
Note: It is assumed that the reader has knowledge of the tree data structure, so the explanation of its implementation will not be deepened.



const LEFT = 0
const RIGHT = 1

class Node {
    constructor(value) {
        this.value = value
        this.children = []
        this.parent = null
        this.pos = { x: 0 , y: 0}
        this.r = 20
    }

    get left() { return this.children[LEFT] }

    set left(value) {
        value.parent = this
        this.children[LEFT] = value
    }

    get right() { return this.children[RIGHT]}

    set right(value) {
        value.parent = this
        this.children[RIGHT] = value
    }

    set position(position){ this.pos = position }

    get position(){ return this.pos }

    get radius() { return this.r }
}

Well, now that we have the node class, we are going to implement the Tree class, which allows inserting the child nodes, their value and position.



class Tree{

    constructor(){
        this.root = null
        this.startPosition = {x: 800, y: 44}
        this.axisX = 350
        this.axisY = 80
    }

    getPosition({x , y}, isLeft = false){
        return { x: isLeft ? x - this.axisX + y : x + this.axisX - y, y: y + this.axisY }
    }

    add(value){
        const newNode = new Node(value)
        if(this.root == null){
            newNode.position = this.startPosition
            this.root = newNode
        } else {
            let node = this.root
                while(node){
                    if(node.value == value)
                        break
                    if(value > node.value){
                        if(node.right == null){
                            newNode.position = this.getPosition(node.position) //get current position of new node
                            node.right = newNode 
                            break
                         }
                         node = node.right
                     } else {
                         if(node.left == null){
                             newNode.position = this.getPosition(node.position,true) //get current position of new node
                             node.left = newNode
                             break
                         }
                         node = node.left
                     }
               }
        }
    }

    // bfs(){ ... } it will be implemented later
}

In the Tree class, 4 attributes are initialized in the constructor, which are:

root attribute refers to the root node of the tree.
startPosition is an attribute used to determine the position on the abscissa axis or X axis and its ordinate or Y axis, of the root node.
axisX and axisY, are numerical constants that allow the nodes to be moved graphically in the plane.
The add method of the Tree class allows inserting a new node in the tree, the position of the node is changed depending on whether it is a left or right node.
getPosition method receives the X and Y position as an argument, isLeft flag by default is false, this method allows to calculate the new position in plane of the new node. The constant axisX is added or subtracted from the X axis together with the position in Y, since in this axis less and less distance will move between nodes, while the depth of the tree is greater. On the other hand, the Y axis only adds the constant axisY, because the distance between the nodes on this axis will always be the same.

Breadth First Search

To graph the binary tree in the plane, it is necessary to go through each node of the tree, for this there are 2 possibilities:

The first is the Depth First Search - DFS, which starts from the root and expands each of the nodes to the end nodes or leaves, for each of the branches, using a stack to temporarily store the nodes while traveling .
The second option is the Breadth First Search - BFS, which starts from the root and traverses each node through levels instead of branches, using a queue to temporarily store nodes.

To graph the tree, I have decided to use the BFS since I prefer to graph the nodes by levels, it is true that when it is required to visit all the nodes of the tree it is better to use DFS since the search by width is efficient in finding the shortest path, however in this case tastes and preferences are far from being technical.

It is time to graph the tree by implementing BFS



var c = document.getElementById("myCanvas")
var ctx = c.getContext("2d")
...
bfs() {
    const queue = []
    const black = "#000"
    queue.push(this.root)

    while (queue.length !== 0) {
        const node = queue.shift()
        const {x, y} = node.position
        const color = "#" + ( (1<<24) * Math.random() | 0 ).toString(16)

        ctx.beginPath()
        ctx.strokeStyle = black
        ctx.fillStyle = color
        ctx.fill()
        ctx.stroke()
        ctx.strokeStyle = black
        ctx.strokeText(node.value, x, y)

        node.children.forEach(child => {
            const {x: x1, y: y1} = child.position
            ctx.beginPath();
            ctx.moveTo(x, y + child.radius)
            ctx.lineTo(x1, y1 - child.radius)
            ctx.stroke()
            queue.push(child)
        });
    }
}

The above algorithm is detailed below:

Create a queue variable, in javascript an array serves this purpose, const queue = [].
Insert root of the tree, queue.push(this.root), into the queue.
As long as the queue has nodes, the following is done.
Remove the first item from the queue and return the item removed const node = queue.shift().
Get the position of the deleted node const {x, y} = node.position, also the following line, calculates a color randomly.
Start a new route by emptying the list of sub-routes, since it is required to create a new route to plot the circumference, ctx.beginPath().
Determine the color of the line, a black color in this case, ctx.strokeStyle = black, and also determine the fill color, ctx.fillStyle = color.
Draw a circle, you have to draw an arc of 360 degrees, that is, 2π radians, for this we use the method ctx.arc(x, y, node.radius, 0, 2 * Math.PI), where X and Y is the center of the circumference, the next parameter is the radius, the 0 represents the starting angle and the last represents the final angle in radians.
Draw the previously defined line ctx.stroke(), and assign the black line again, ctx.strokeStyle = black.
Write the value of the node ctx.strokeText(node.value, x, y), in the same position on the circumference.
For each child node that the parent node has (node.children.forEach) the following is done:
Gets the position of the child node const {x: x1, y: y1} = child.position.
Draw a line from the parent node (ctx.moveTo (x, y + child.radius)), to the child node (ctx.lineTo (x1, y1 - child.radius)) joining the edges of each circumference.
Add the child node to the queue.push(child).

Ready!. The method to graph the tree is implemented, it is time to put into operation the insert and graph methods of the tree class.



const t = new Tree()
t.add(10)
t.add(5)
t.add(15)
t.add(3)
t.add(14)
t.add(16)
t.add(4)
t.add(6)
t.add(2)
t.bfs()

The result of the execution of the previous code will be the following.

This source code can be found on GitHub.

Was it useful? Show your support or share it!

Thank you!!

Mandelbrot Set in JS - Zoom In

Fabian Quijosaca — Tue, 26 May 2020 04:03:59 +0000

In the previous blog, I explained a little bit about the theory behind the mandelbrot set, also I implemented a JavaScript version to plot it. In this blog I will show you, how to make the zoom effect on the set, using JavaScript and Workers.

The result of the zoom in will be as follows:

Now that you have just watched the video I know that you are very interested and curious, about it, so let's begin!.

I had thought this would be easy, however, it was complicated for several reasons that I summarize below:

The code implemented in the previous blog was very inefficient O(n*m) in terms of time, also known as time complexity, which caused the amount of time needed to plot the entire canvas become too high.
Despite several improvements I made to the algorithm, it was still very inefficient, so I decided to use workers.

Let's see how I solved the problems presented above.

Mandelbrot set

As usual with me, I will explain each piece of code used.

Some of code blocks were already explained in the previous blog, so I'm just going to focus on the new ones.

I declare worker to store the reference to my worker class, colorPalette to store a rgb colors, ZOOM_FACTOR, it's a scaling factor for the zoom in, and the last one is TASK, I will use it to save the index of each column of my canvas (I will enter into detail later).

const canvas = document.getElementById('myCanvas')
const ctx = canvas.getContext('2d')

const WIDTH = 800
const HEIGHT = 600
ctx.canvas.width = WIDTH
ctx.canvas.height = HEIGHT

let worker
let colorPalette = []
let REAL_SET = { start: -2, end: 1 }
let IMAGINARY_SET = { start: -1, end: 1 }
const ZOOM_FACTOR = 0.1
const TASKS = []

I decided to create a different palette color so I have used a simplified version of interpolation to create different colors.

const lagrange = ([X1, Y1], [X2, Y2], x) =>
   (((Y1 * (x - X2)) / (X1 - X2)) + ((Y2 * (x - X1)) / (X2 - X1)))

const makeRGB = (r, g, b, k) => {
    const calculate = pair => parseInt(lagrange(pair[0], pair[1], k))
    if (isNaN(r)) r = calculate(r)
    if (isNaN(g)) g = calculate(g)
    if (isNaN(b)) b = calculate(b)

    return [r, g, b]
}

const palette = (size = 250) => {
    const range = parseInt(size / 6)
    const colors = []
    let c
    for (let k = 0; k < size; k++) {
        if (k <= range)//red to yellow
            c = makeRGB(255, [[0, 0], [range, 255]], 0, k)
        else if (k <= range * 2)//yellow to green
            c = makeRGB([[range + 1, 255], [range * 2, 0]], 255, 0, k)
        else if (k <= range * 3)//green to cyan
            c = makeRGB(0, 255, [[range * 2 + 1, 0], [range * 3, 255]], k)
        else if (k <= range * 4)//cyan to blue
            c = makeRGB(0, [[range * 3 + 1, 255], [range * 4, 0]], 255, k)
        else if (k <= range * 5)//blue to purple
            c = makeRGB([[range * 4 + 1, 0], [range * 5, 255]], 0, 255, k)
        else//purple to red
            c = makeRGB(255, 0, [[range * 5 + 1, 255], [size - 1, 0]], k)

        colors.push(c)
    }
    return colors
}

In the previous code block, the function palette is creating 250 colors. The interpolation is done between 6 colors, those are: RED - YELLOW - GREEN - CYAN - BLUE - PURPLE
What result in a color palette called rainbow colors.

To improve time complexity in plot function, I will store in an array each column index; after that, the first index of the column will be sent (postMessage) to a worker which will calculate the values of each point that belongs to the rows.
In summary, only one line of each column of the mandelbrot set will be calculated at once.

const start = () => {
    for (let col = 0; col < WIDTH; col++) TASKS[col] = col
    worker.postMessage({ col: TASKS.shift() })
}

In the next code is explained how the rest of lines are calculated and plotted.

const draw = res => {
    if (TASKS.length > 0)
        worker.postMessage({ col: TASKS.shift() })

    const { col, mandelbrotSets } = res.data
    for (let i = 0; i < HEIGHT; i++) {
        const [m, isMandelbrotSet] = mandelbrotSets[i]
        c = isMandelbrotSet ? [0, 0, 0] : colorPalette[m % (colorPalette.length - 1)]
        ctx.fillStyle = `rgb(${c[0]}, ${c[1]}, ${c[2]})`
        ctx.fillRect(col, i, 1, 1)
    }
}

The draw function will receive the response of the worker as parameter, this contains the mandelbrot set values for a specific column. If there are still column values to calculate, a message with next column index is sent to worker. Then the line of values that has been calculated by the worker is drawn on the canvas.
This function will be called over and over again, as a recursive process, since the worker listens to the messages that are sent from this function and this in turn, listens to the messages sent by the worker, as long as there are column values to be processed.

Well, it's time to create the function that orchestrates each of the functions explained so far.

const init = () => {
    if (worker) worker.terminate()
    worker = new Worker('worker.js')
    worker.postMessage({ w: WIDTH, h: HEIGHT, realSet: REAL_SET, imaginarySet: IMAGINARY_SET, isSettingUp: true })
    start()
    colorPalette = palette()
    worker.onmessage = draw
}

I have called init to the function, which will be the first to run.
If worker already exists, this thread is killed.
After this, a new worker is created, then a message is sent to the worker, this first message is only to send the necessary parameters for the mandelbrot set computations.

Once the worker has been configured, the start function is executed.

Finally, draw function will listen the worker messages, worker.onmessage = draw, is a function to be called when the message event occurs.

Adding worker

Due to performance issues discussed at the beginning, the heaviest task that is mandlebrot set computations is moved to a worker.

//worker.js
let WIDTH, HEIGHT, REAL_SET, IMAGINARY_SET, END_START_RL, END_START_IM
const MAX_ITERATION = 1000

onmessage = e => {
    const { isSettingUp } = e.data
    if (isSettingUp) {
        const { w, h, realSet, imaginarySet } = e.data

        REAL_SET = { start: realSet.start, end: realSet.end }
        IMAGINARY_SET = { start: imaginarySet.start, end: imaginarySet.end }

        END_START_RL = (REAL_SET.end - REAL_SET.start)
        END_START_IM = (IMAGINARY_SET.end - IMAGINARY_SET.start)

        WIDTH = w
        HEIGHT = h
    } else {
        const { col } = e.data
        const mandelbrotSets = []
        for (let row = 0; row < HEIGHT; row++)
            mandelbrotSets[row] = calculate(col, row)

        postMessage({ col, mandelbrotSets })
    }
}

const calculate = (i, j) => mandelbrot(relativePoint(i, j))

const relativePoint = (x, y) => {
    x = REAL_SET.start + (x / WIDTH) * (END_START_RL)
    y = IMAGINARY_SET.start + (y / HEIGHT) * (END_START_IM)

    return { x, y }
}

const mandelbrot = (c) => {
    let z = { x: 0, y: 0 }, n = 0, p, d;
    do {
        p = {
            x: Math.pow(z.x, 2) - Math.pow(z.y, 2),
            y: 2 * z.x * z.y
        }
        z = {
            x: p.x + c.x,
            y: p.y + c.y
        }
        d = 0.5 * (Math.pow(z.x, 2) + Math.pow(z.y, 2))
        n += 1
    } while (d <= 2 && n < MAX_ITERATION)

    return [n, d <= 2]
}

The function onmessage, will listen for the messages that are sent from the main thread.
If is setting up, the necessary parameters for the computations are saved in the global variables and it does not send any message.

Otherwise, the values for the set are calculated for each of the columns, then those values are sent to main thread as response.

The functions relativePoint and mandelbrot were already explained in the previous blog.

Zoom In

We have already improved the time it takes to plot the mandelbrot set, but How the hell do I zoom in over this image?

Well, the answer is simple, it is only necessary to shrink the real and imaginary values each time that a specific part of the canvas is clicked.

Let's see the range of values that have the real and imaginary part:

REAL_SET: the domain in x axis goes from -2 to 1.
IMAGINARY_SET: the domain in y axis goes from -1 to 1.

So, the idea is to decrease each of the values that the set can take in both the real and imaginary parts.

For instance:

REAL_SET: start -1, end: 0.5
IMAGINARY_SET: start -0.5, end: 0.5

This is what the following function does every time that double click event occurs on a specific part of the canvas, according to a scaling factor (ZOOM_FACTOR).

//mandelbrot.js
canvas.addEventListener('dblclick', e => {
    const zfw = (WIDTH * ZOOM_FACTOR)
    const zfh = (HEIGHT * ZOOM_FACTOR)

    REAL_SET = {
        start: getRelativePoint(e.pageX - canvas.offsetLeft - zfw, WIDTH, REAL_SET),
        end: getRelativePoint(e.pageX - canvas.offsetLeft + zfw, WIDTH, REAL_SET)
    }
    IMAGINARY_SET = {
        start: getRelativePoint(e.pageY - canvas.offsetTop - zfh, HEIGHT, IMAGINARY_SET),
        end: getRelativePoint(e.pageY - canvas.offsetTop + zfh, HEIGHT, IMAGINARY_SET)
    }

    init()
})

const getRelativePoint = (pixel, length, set) =>
   set.start + (pixel / length) * (set.end - set.start)

Results

That's it, when you press double click on any part of the canvas, you will see the following images.

Figure 1. Mandelbrot set, example 1.

Figure 2. Mandelbrot set, example 2.

Figure 3. Mandelbrot set, example 3.

Figure 4. Mandelbrot set, example 4.

Figure 5. Mandelbrot set, example 5.

Figure 6. Mandelbrot set, example 6.

Figure 7. Mandelbrot set, example 7.

Figure 8. Mandelbrot set, example 8.

I encourage you to play around by modifying the color palette and zoom factor, for example try using the black and white color palette.

I hope you enjoyed!.

Full code

Live demo

Stay safe and thank you so much for reading!

The Water Jug Riddle in JS

Fabian Quijosaca — Fri, 01 May 2020 22:53:46 +0000

In this entry I want to share you, how to solve the water jug riddle using Javascript, by the way a curious fact, this problem is featured in the film Die Hard. So, the riddle is:

You have 2 jugs, 5 and 3 liters of capacity respectively, without any measurement mark, in addition you have an unlimited water source that allows you to fill the jugs with water. Exactly 4 liters of water is required in one of the jugs.

Note: The same problem is explained in this entry and is implemented in Prolog (Spoiler: is in spanish).

First of all, we should answer the following question, How would we solve this manually?

In order to measure the 4 liters required, a set of steps must be executed, we suppose that, the initial state is 0 liters of water in the large and small jug.

1. First, fill the large jug.

2. Once the 5-liter jug is full, pour the content of the large jug into the small one, resulting in 2 and 3 liters of water; now the small jug is full.

3. Empty the small jug.

4. Pour the contents of the large jug into the small jug. The large jug contains 0 liters of water and 2 liters the small jug.

5. Fill the large jug, again.

6. Pour the content of the large jug into the small one where there is 2 lt of water. Since it only takes one liter to fill the small jug and the large jug contains 5 lt of water. As you pass from the large jug into the small jug, 4 liters of water results in the large jug.

Finally, in this step the problem has been solved in 6 steps, it should be mentioned that this is not the unique solution, since there are more, for example, you can start by filling the small jug (3lt).

Implementation in JS

To represent each state of the jugs, I'm going to use an object, it has two properties, small and large, of type integer.

const state = { small: 0, large: 0 }

In the following code, 4 functions are written to modify the jugs states.

const MAX_LARGE = 5
const MAX_SMALL = 3

const fillJug = (jugs, key = 'large', max = MAX_LARGE) => ({ ...jugs, [key]: max })

const emptyJug = (jugs, key = 'large') => ({ ...jugs, [key]: 0 })

const largeToSmall = ({ large, small }) => {
    const quantityNeededToFillSmall = MAX_SMALL - small

    return {
        large: large > quantityNeededToFillSmall
            ? large - quantityNeededToFillSmall : 0,
        small: large > quantityNeededToFillSmall
            ? small + quantityNeededToFillSmall : small + large
    }
}

const smallToLarge = ({ large, small }) => {
    const quantityNeededToFillLarge = MAX_LARGE - large

    return {
        large: small > quantityNeededToFillLarge
            ? small - quantityNeededToFillLarge : 0,
        small: small > quantityNeededToFillLarge
            ? large + quantityNeededToFillLarge : small + large
    }
}

const isRepeated = (path, { small, large }) =>
    !!path.find(x => x.small === small && x.large === large)

The first 2 lines are constants to define the maximum capacity of jugs.

fillJug, this function will modify the jugs state, filling one of them by its key, both jugs and key are passed as parameters, refer to explanation 1 and 5 of this entry.
emptyJug, it'll empty a jug, put state in 0, small or the large one, as point 3 of the previous explanation.
largeToSmall, pour the content of the large jug into the small one.
- quantityNeededToFillSmall, is self explanatory.
- large, if the quantity of water in the large jug is greater than quantity needed to fill the small one, subtract the quantity of water from the large jug and the quantity needed to fill the small one (large - quantityNeededToFillSmall), it means not all the content of the large jug will be poured into the small one. Otherwise, it'll be zero, because it means that all the content of the large jug are poured into the small one.
- small, if the quantity of water in the large jug is greater than quantity needed to fill the small one means, the small jug doesn't have the capacity to store all the content of the large jug, so is added just the quantity of the small jug and the quantity needed to fill it (small + quantityNeededToFillSmall). Otherwise, all of the content from the large jug will be poured into the small one (small + large).
smallToLarge, pour the content of the small jug into the large one. The rest is similar to the previous explanation, but in reverse.
isRepeated, will check if the new state already exists in path.

To find the path to the solution, Breadth-First Search (BFS) is proposed, because is the most efficient algorithm to find the shortest path, this algorithm begins from the root and goes through each node by levels instead of branches as Deep-First Search (DFS) does, using a queue to temporarily store nodes.

BFS is implemented to find the shortest path.

function getShortestPath(start, target) {

    const queue = []
    const path = []

    path.push(start)
    queue.push(path)

    while (queue.length) {
        const lastPath = queue.shift()
        const lastState = lastPath[lastPath.length - 1]

        if (target === lastState.large)
            return lastPath

        const states = new Set([fillJug(lastState), fillJug(lastState, 'small', MAX_SMALL),
        largeToSmall(lastState), smallToLarge(lastState), emptyJug(lastState), emptyJug(lastState, 'small')])

        for (let item of states) {
            if (!isRepeated(lastPath, item)) {
                const newPath = [...lastPath]
                newPath.push(item)
                queue.push(newPath)
            }
        }
    }

    return null
}

path = getShortestPath(state, 4)

console.log(path)

getShortestPath, receives two parameters, the first one is the initial state of the jugs, and the second one is the final quantity needed.
Declare an array (queue), which will be used as a queue to store the shortest path.
Declare an array (path), to store the selected states.
Add the initial state as the first element of the path array, path.push(start), then this path is added to the queue.
While data exists in the queue, while(queue.length), the following instructions are executed.
- The first element of the queue is removed (queue.shift()), and stored in lastPath variable.
- The last state is selected from the last path array (lastState = lastPath[lastPath.length - 1]).
- If the quantity in the large jug (last state) selected is equal to target value that you are looking for, it returns the list of obtained state (shortest path) (return lastPath). Otherwise it'll continue.
- We add the possible states that can be generated from the last one, to a Set data structure.
- For each state obtained in the previous step, the next instructions are executed.
- It's reviewed that the generated state isn't yet included in the path (solution path).
- In case the previous condition is met, create a new list (new path) with the states of the last path.
- In this new path is added the new state of the jugs (newPath.push(item)), afterwards the new path is added to queue.
Finally, if during the repetitive cycle the target state is not found, it returns null.

When executing the previous code, the following is printed in console.

path = getShortestPath(state, 4)

console.log(JSON.stringify(path, null,'\t'))
// console output
[
    { "large": 0, "small": 0 },
    { "large": 5, "small": 0 },
    { "large": 2, "small": 3 },
    { "large": 2, "small": 0 },
    { "large": 0, "small": 2 },
    { "large": 5, "small": 2 },
    { "large": 4, "small": 3 }
]

I hope you've enjoyed!.

Full Code

It's my second blog, written entirely in English (I'm not a native speaker), maybe you've already realized, so sorry for the misspellings!, please If you have any recommendation, or comment you can leave in the comments section.

Stay safe and thanks for reading!

Mandelbrot Set in JS

Fabian Quijosaca — Fri, 24 Apr 2020 01:47:36 +0000

In this entry I want to share with you, a little of my knowledge to show you how to plot a Mandelbrot Set without any library just JS, so go ahead!.

Note: If you are not familiar with the mathematical terms used here, I recommend you to read about complex numbers and fractals.

First of all, What a heck is a Mandelbrot Set?, according to mathworld:

A Mandelbrot Set, is used to refer both to a general class of fractal sets and to a particular instance of such a set. In general, a Mandelbrot set marks the set of points in the complex plane such that the corresponding Julia set is connected and not computable.

In a nutshell, a mandelbrot set is one of the most beautiful and famous fractal, that is defined by the set of complex numbers.

In the next picture you can see what I mean.

Figure 1: Mandelbrot set - black and white

In this entry you will learn how to plot in JS, the previous image.

But before, let's see a little more theory about how this set works.

Definition

As we mention before, the mandelbrot set is defined in the set of complex numbers c for which the function,

does not diverge when iterated from z = 0.

Below, the previous equation is broken down:

As you can see, the Mandelbrot set is obtained from the quadratic recursive equation where, z and c represents a complex number.

To represent visually this set we need to find, for each point c
of a part of the complex plane, if Zn is bounded. When the modulus of Zn is greater than 2, means that the number does not belong to Mandelbrot set, otherwise it is part of the set. The number of iterations to reach a modulus greater than 2 can be used to determine the color to use when we are plotting.

A complex plane can be represented in a normal 2D plane, where the X axis, will represent the real number, meanwhile the Y axis will represent the imaginary number, for instance, x = 3; y= 5i.

For a better understanding please refer to this video.

Plot of the Mandelbrot Set

Finally, after understand a bit of the Mandelbrot equation, it's time to implement it:



const MAX_ITERATION = 80
function mandelbrot(c) {
    let z = { x: 0, y: 0 }, n = 0, p, d;
    do {
        p = {
            x: Math.pow(z.x, 2) - Math.pow(z.y, 2),
            y: 2 * z.x * z.y
        }
        z = {
            x: p.x + c.x,
            y: p.y + c.y
        }
        d = Math.sqrt(Math.pow(z.x, 2) + Math.pow(z.y, 2))
        n += 1
    } while (d <= 2 && n < MAX_ITERATION)
    return [n, d <= 2]
}

The mandelbrot function receives a complex number, it has real and imaginary part, here we are representing those components as x and y.
The p variable contains the computing of the square of z, which is also a complex number, please refer to this, to understand how basic operations such as addition, subtraction and multiplication works in complex numbers.
z is recalculated and now it contains the addition of the received complex number (c) and the previous z.
d is the modulus of the new complex number (z), computed before.
Add one when each iteration is completed (n += 1).
The whole process is repeated while the modulus of z belongs to Mandelbrot set and the iteration number is less than 80.
Finally, the function returns a tuple, with the iteration number that it took to reach a modulus greater than 2, and whether the complex number passed to it, belongs to Mandelbrot set.

And that's it!, we have implemented a mandelbrot equation.
Now is time to plot.



var canvas = document.getElementById('myCanvas')
var ctx = canvas.getContext('2d')

const WIDTH = window.innerWidth
const HEIGHT = window.innerHeight
ctx.canvas.width = WIDTH
ctx.canvas.height = HEIGHT

const REAL_SET = { start: -2, end: 1 }
const IMAGINARY_SET = { start: -1, end: 1 }

const colors = new Array(16).fill(0).map((_, i) => i === 0 ? '#000' : `#${((1 << 24) * Math.random() | 0).toString(16)}`)

function draw() {
    for (let i = 0; i < WIDTH; i++) {
        for (let j = 0; j < HEIGHT; j++) {
            complex = {
                x: REAL_SET.start + (i / WIDTH) * (REAL_SET.end - REAL_SET.start),
                y: IMAGINARY_SET.start + (j / HEIGHT) * (IMAGINARY_SET.end - IMAGINARY_SET.start)
            }

            const [m, isMandelbrotSet] = mandelbrot(complex)
            ctx.fillStyle = colors[isMandelbrotSet ? 0 : (m % colors.length - 1) + 1]
            ctx.fillRect(i, j, 1, 1)
        }
    }
}

In the first lines, the canvas element is found and its context, then the window width and height is assigned to the canvas.
REAL_SET constant represent the real numbers of Mandlebrot set, as you saw the Figure 1 of this entry, the domain in x axis goes from -2 to 1.
IMAGINARY_SET represent, the imaginary numbers in y axis, the domain in y axis goes from -1 to 1.
colors, store a list of 16 random hexadecimal colors.
draw function:
- The entire width and height of the canvas are iterated.
- The "complex" variable store a complex number; x and y, are calculated getting a relative value, of the width and height of the canvas, plus the values that belong to the mandelbrot set.
- mandelbrot function is called
- A color is assigned to canvas pixel, if the complex number passed to mandelbrot function belongs to set, the black color is chosen, otherwise the color depends of the number of iteration made by mandelbrot function.
- A pixel (rectangle of 1 width and height) is plotted in the position i, j.

That's all, we've finished, it was so easy! isn't it?

If we run the code, it shows the next figures.

Figure 2. Mandelbrot set, example 1.

Figure 3. Mandelbrot set, example 2.

Figure 4. Mandelbrot set, example 3.

Figure 5. Mandelbrot set, example 4.

Figure 6. Mandelbrot set, example 5.

I hope you've enjoyed!.

Live demo
Full code

By the way, It's my first blog, written entirely in English (I'm not a native speaker), maybe you've already realized, so sorry for the misspellings!, please If you have any recommendation, or comment you can leave in the comments section.

Next steps

Our fractal is plotted, so in the next entry I will implement the zoom, when a part of the image is clicked.

Stay safe and thanks for reading!

Prolog: Acertijo del granjero, la cabra, el lobo y la col

Fabian Quijosaca — Sat, 28 Mar 2020 22:49:24 +0000

En un blog anterior se resolvió, el problema de razonamiento denominado jarras de agua; con el lenguaje de programación Prolog, en este blog se sige con esa misma línea y se explica sobre la resolución de un popular juego de lógica llamado el acertijo del granjero, el lobo, la cabra y la col (hay un capítulo de los simpsons donde Homero resuelve un acertijo similar, para aquellos curiosos); el cual menciona lo siguiente:

"Hace mucho tiempo un granjero fue al mercado y compró un lobo, una cabra y una col. Para volver a su casa tenía que cruzar un río. El granjero dispone de una barca para cruzar a la otra orilla, pero en la barca solo caben él y una de sus compras. Si el lobo se queda solo con la cabra se la come, si la cabra se queda sola con la col se la come. El reto del granjero era cruzar él mismo y dejar sus compras a la otra orilla del río, dejando cada compra intacta." ¿Cómo lo hizo?

Como se mencionó en el blog anterior es necesario entender el problema, en este aspecto particular, basta con la descripción y el gráfico realizado en la parte de arriba, sin embargo lo que aún no está claro es cómo el granjero logró resolver el problema, por tanto a continuación se describe detalladamente la solución.

El primer paso es llevar la cabra a través del río, evitando que la cabra o la col sean devoradas. Cuando el granjero vuelve a la orilla de partida, debe elegir entre llevar la col o al lobo. Si lleva al lobo, debe volver para llevar la col, entonces el lobo se comería a la cabra. Si lleva la col al otro lado, debe volver para llevar al lobo, entonces la col sería comida. He aquí el problema, el cuál se resuelve con los siguientes 7 pasos:

1. Deja a la cabra al otro lado
2. Regresa al punto de partida (sólo el granjero)
3. Deja al lobo al otro lado
4. Regresa con la cabra
5. Deja la col al otro lado
6. Regresa al punto de partida (sólo el granjero)
7. Deja la cabra al otro lado

Se realizan cuatro viajes hacia la derecha y tres hacia la izquierda.

Cabe mencionar que esta no es la única solución, dado que existe una segunda alternativa, por ejemplo, en el tercer paso se puede dejar la col al otro lado y regresar con la cabra, luego dejar al lobo al otro lado y regresar solo, y finalmente regresar por la cabra.

Una vez claro el dilema, es momento de implementar dicha solución en Prolog.

Solución en Prolog

Para empezar con el código, antes es necesario definir las variables con las que se va a trabajar.

I= Izquierda, D= Derecha
GR= Granjero, CB= Cabra
LB= Lobo, CL= Col

Definido las variables, se parte de tres hechos, el primero es que el estado deseado final del granjero, la cabra, el lobo y la col terminen en la orilla izquierda asumiendo que todos parten del lado derecho , para lo cual en Prolog se representa de la siguiete manera:

meta(estado(izq, izq, izq, izq)).

La notación anterior indica que el estado final (meta) es que los cuatro actores de este acertijo terminen en la orilla izquierda, sin importar la posición inicial. La estructura estado recibe 4 argumentos que representan la posición en la que se encuentran cada uno de los actores del problema en el siguiente orden; en el primer argumento el granjero, en el segudo la cabra, el tercero el lobo y en el cuarto la col.

Nota 1: Es importante mencionar que para hacer uso del predicado estado se respetará el orden mencionado anteriormente (estado(GR, CB, LB, CL)).

El segundo y tercer hecho son la dirección de los movimientos que pueden realizar, en este caso solo hay dos posibilidades desde la derecha hacia la izquierda o vicerversa, por tanto definiré mi predicado con el nombre de "direccion" como se muestra a continuación.

direccion(izq, der).
direccion(der, izq).

Los hechos anteriores describen la siguiente relación, la dirección en la que puede moverse es desde la izquierda hacia la derecha y desde la derecha hacia la izquierda.
A continuación se definen varias reglas dado que un hecho puede depender de la verdad de otro hecho o conjunto de hechos, esto es que se va a definir los predicados para los posibles movimientos que puede hacer el granjero.

1.- Un movimiento a realizar es que el granjero cruce el río solo, en cualquier dirección, lo que en prolog se traduce en la siguiente regla:

movimiento(estado(M, CB, LB, CL), estado(M1, CB, LB, CL)):- direccion(M, M1).

La regla anterior menciona que el granjero se mueve de una orilla hacia la otra, si éste se mueve de deracha a izquierda o viceversa (direccion(M, M1).), además se puede apreciar claramente que los argumentos del "movimiento" son 2 estados, el primer estado que toma es estado(M, CB, LB, CL), que quiere decir que en el punto origen se encuentran el Granjero (M), la cabra (CB), el lobo (LB) y la col (CL); el segundo argumento es el estado en el punto destino estado(M1, CB, LB, CL); en donde el argumento del estado M1, indica que cambia solo el estado del granjero (sé que cambia el estado del granjero ya que el primer argumento del estado es utilizado para él, por ejemplo si quisiera que además cambie de estado la cabra, también debería cambiar el segundo argumento que toma el estado a M y M1, ver nota 1).

Nota 2: En el primer y segundo predicado en la posición del granjero, "estado" toma en el primero argumento el valor M y M1 respectivamente, ya que este me indetificará la dirección del movimiento a realizar. El cuerpo de la regla (direccion(M, M1)) indica que el movimiento se realiza si cumple la dirección indicada, es decir, si se mueve de derecha hacia la izquierda o lo contrario; por eso se indica en el argumento de dirección, que cambia M a M1 (los nombre de variables M y M1, pueden tomar cualquier otro nombre).

2.- El siguiente movimiento que puede hacer el granjero, es cruzar el río con el lobo, de nuevo en cualquier dirección:

movimiento(estado(M, CB, M, CL), estado(M1, CB, M1, CL)):- direccion(M, M1).

La regla anterior describe que el granjero y el lobo cruzan el río en una dirección determinada, por eso el cambio de nombre de variabe de GR y LB a M y M1; el análisis de la regla es similar al punto anterior.

3.- Un tercer movimiento del granjero es que cruce el río con la cabra.

movimiento(estado(M, M, LB, CL), estado(M1, M1, LB, CL)):- direccion(M, M1).

4.- El último movimiento que puede hacer el granjero es cruzar el río con la col.

movimiento(estado(M, CB, LB, M), estado(M1, CB, LB, M1)):- direccion(M, M1).

Bien, hasta este punto le hemos dicho a Prolog los movimientos que puede realizar el granjero, sin embargo hace falta especificar los movimiento que no debe hacer el granjero para cruzar el río con todas sus compras a salvo.

5.- Un estado prohibido una vez realizado el movimiento es que el granjero no puede estar al lado contrario del lobo y la cabra.

prohibido(estado(M, M1, M1, _)):- direccion(M, M1).

He creado un predicado denominado "prohibido", que recibe como argumento un "estado", para especificar que el el granjero esta al otro lado de la orilla de donde están el lobo y la cabra, he pasado en el primer argumento del estado, la posición M del granjero, y en el segundo y tercer argumento la misma posición M1 del lobo y la cabra, el símbolo "_", es una variable anónima que significa en este caso que no me interesa la posición en la que se encuentre la col, el cuerpo de la regla (direccion(M, M1)),indica la dirección en la que están.

6.- Otro estado prohibido es que la cabra y la col esten al otro lado del granjero.

prohibido(estado(M, M1, _, M1)):- direccion(M, M1).

Lista de estados

La solución al acertijo es una lista de estados (los que fueron analizados anteriormente) y es conveniente determinar que no existan estados repetidos, por tanto hay que verificar si un elemento pertenece a una lista, en Prolog se define de la siguiente manera:

miembro(X, [X|_]).
miembro(X, [_|L]):- miembro(X, L).

Solución

A continuación, se define la solución a este acertijo:

E = cabeza de la lista L = cola de la lista

solucion([E | L], [E | L]) :- meta(E).

Esta regla anterior permite determinar la solución base (definida con el mismo nombre sin acento) recibe 2 listas como parámetros, que deben ser iguales para ser la solución ([E | L], [E | L]), mismas que se dividen en cabeza y cola ([E | L]). La meta recibe la cabeza de la lista el cual es un estado que anteriormente ya se definió para que sea solución meta(estado(izq, izq, izq, izq)), en el caso que no sea la solución base se define la siguiente regla:

solucion([E | L], LS):- movimiento(E, EP), not(prohibido(EP)), not(miembro(EP, L)), solucion([EP, E | L], LS).

Esta regla permite añadir a la lista de soluciones un nuevo estado (EP) si cumple las siguientes condiciones:

Es un movimiento permitido (movimiento(E, EP))
No es un estado prohibido (not(prohibido(EP)))
No se encuentra un estado igual en la lista de solucioines (not(miembro(EP, L)))

Nota 3: La variable LS, almacena el resultado, es decir la lista de estados que permiten llegar a la solución, el cual prolog mostrará como salida.

Si cumple con las condiciones anteriores, el nuevo estado posible es añadida a la lista de soluciones ([EP, E | L]), esto se repite recursivamente hasta encontrar el caso base (solucion([EP, E | L], LS)), y listo!.

Para ejecutar el programa en Prolog, se lo hace de la siguiente manera:

solucion([estado(der, der, der, der)], L).

La solución recibe una lista de estados, en este caso he puesto solo un elemento en la lista (estado(der, der, der, der)), y en este estado todos los actores del problema están en la parte derecha de la orilla del río, en la variable L se almacenara la lista de estados. Al ejecutar en prolog me muestra dos soluciones que son las siguientes:

L = [estado(izq, izq, izq, izq), estado(der, der, izq, izq), estado(izq, der, izq, izq), estado(der, der, izq, der), estado(izq, izq, izq, der), estado(der, izq, der, der), estado(izq, izq, der, der), estado(der, der, der, der)]
L = [estado(izq, izq, izq, izq), estado(der, der, izq, izq), estado(izq, der, izq, izq), estado(der, der, der, izq), estado(izq, izq, der, izq), estado(der, izq, der, der), estado(izq, izq, der, der), estado(der, der, der, der)]

A continuación se muestra todo el código:

meta(estado(izq, izq, izq, izq)).
direccion(izq, der).
direccion(der, izq).

/*  Movimientos permitidos */
movimiento(estado(M, CB, LB, CL), estado(M1, CB, LB, CL)):- direccion(M, M1).
movimiento(estado(M, CB, M, CL), estado(M1, CB, M1, CL)):- direccion(M, M1).
movimiento(estado(M, M, LB, CL), estado(M1, M1, LB, CL)):- direccion(M, M1).
movimiento(estado(M, CB, LB, M), estado(M1, CB, LB, M1)):- direccion(M, M1).

/*  Movimientos prohibidos */
prohibido(estado(M, M1, M1, _)):- direccion(M, M1).
prohibido(estado(M, M1, _, M1)):- direccion(M, M1).

/*  Verifica si un elemento pertenece a una lista */
miembro(X, [X|_]).
miembro(X, [_|L]):- miembro(X, L).

/*  Solución */ 
solucion([E | L], [E | L]) :- meta(E).
solucion([E | L], LS):- movimiento(E, EP), not(prohibido(EP)), not(miembro(EP, L)), solucion([EP, E | L], LS).

También pueden encontrar el mismo código en GitHub.

Con esto concluimos, en casos de dudas pueden contactarme a fabianq44@gmail.com.

¡Gracias por su lectura!

Prolog: Acertijo jarras de agua

Fabian Quijosaca — Mon, 23 Mar 2020 03:09:07 +0000

Al empezar a aprender Prolog, surgen ejercicios de razonamiento como el acertijo de las jarras de agua, el cual menciona que se tiene 2 jarras, de 5 y 3 litros de capacidad respectivamente, sin ninguna marca de medición, además se tiene una fuente de agua ilimitada que permite llenar las jarras de agua. Se requiere exactamente 4 litros de agua en una de las jarras. En este blog se explica la resolución del acertijo.

Hay que tener en cuenta 3 aspectos fundamentales antes de programar el acertijo en cualquier lenguaje de programación; y estos son los siguientes:

1. Es necesario entender el problema.
2. Resolver el problema, esto se lo puede hacer mentalmente o como yo, que prefiero plasmar la resolución sobre una hoja de papel, mediante gráficos que ayuden a entender mejor la resolución del acertijo.
3. Por último, una vez que haya resuelto el acertijo o problema, es momento de plasmar la solución utilizando un lenguaje de prgramación, Prolog en este caso.

Para resolver este acertijo se va a utilizar los 3 aspectos recomendados en el punto anterior.

1. ¿Cuál es el problema?

No se puede medir exactamente los 4 litros de agua dado que se dispone de 2 jarras de 5 y 3 litros sin marcas de medición.

2. ¿Cómo resuelvo el problema?

Para lograr medir los 4 litros necesarios, se requiere realizar un conjunto de pasos, veamos:
Se puede partir llenando cualquiera de las 2 jarras, la jarra grande (5lt) o jarra pequeña (3lt), por ejemplo, se llena primero la jarra grande.

Una vez lleno la jarra de 5 litros, se vierte el contenido de la jarra grande en la pequeña, dando como resultado, 2 y 3 litros de agua; la jarra pequeña queda llena.

Como tercer paso, se vacía la jarra pequeña.

En el cuarto paso, se vierte el contenido de la jarra grande donde hay 2lt de agua a la jarra pequeña, quedando al final 0 litros de agua en la jarra grande y 2 litros en la jarra pequeña.

En el quinto paso, se llena nuevamente la jarra grande.

En el paso 6, que es el último, se vierte el contenido de la jarra grande a la pequeña donde hay 2lt de agua, dado que solo falta un litro para llenar la jarra pequeña; y la jarra grande contiene 5 litros de agua, al pasar de la jarra grande a la pequeña, resulta 4 litros de agua en la jarra grande.

En este paso se ha resuelto el problema en 6 pasos, cabe mencionar que esta no es la única solución, dado que existen varias soluciones, por ejemplo, se puede partir llenando la jarra pequeña (3lt).

3. Programar solución

En este punto esta claro lo que se va a programar, el objetivo de este tutorial no es enseñar cómo funciona Prolog, al contrario se entiende que el lector tiene conocimientos, al menos básicos sobre este lenguaje de programación lógico e interpretado.

Se parte de un hecho, donde el estado deseado es que la jarra grande (5lt) contenga 4 litros de agua como estado final, para lo cual en Prolog se representa de la siguiete manera:



estado(4, _ )

Donde, el número 4 representa la cantidad de agua en la jarra grande y el símbolo ( _ ) representa que no interesa el valor en la jarra pequeña (3lt), este estado final se lo representará como el siguiente hecho:



meta(estado(4, _ )).

Para continuar, es necesario definir las variables con las que se va a trabajar, por tanto, a continuación se define las siguientes variables:

CJG = cantidad de agua en la jarra grande
CJP = cantidad de agua en la jarra pequeña
MJG = capacidad máxima de la jarra grande (5lt)
MJP = capacidad máxima de la jarra pequeña (3lt)

A continuación es necesario definir todas las reglas (8 reglas) para la resolución del acertijo, donde la verdad de un hecho depende de la verdad de otro hecho o conjunto de hechos. Un estado posible dependerá de un conjunto de reglas, por ejemplo:

1. El estado posible puede ser que la jarra grande quede llena, y este hecho se representa de la siguiente manera en Prolog:



posible(estado(CJG , CJP), estado(CJG1, CJP), MJG, _)

Dado que las reglas se componen de una cabeza y un cuerpo, falta definir el cuerpo de esta regla, que es nada más que otro conjunto de hechos. Para el posible estado mencionado anteriormente se define ciertas condiciones y estas son: CJG >= 0, CJG < MJG, CJG1 is MJG, el símbolo ( , ) representa un AND en prolog y el ( . ) el final de un predicado, la palabra reservada is representa la igualdad ( = ), por tanto, la regla completa queda de la siguiente manera:



posible(estado(CJG, CJP), estado(CJG1, CJP), MJG, _) :- CJG >= 0, CJG < MJG, CJG1 is MJG .

Esta expresión se lee de la siguiente manera, solo se puede llenar la jarra grande, si la jarra no esta llena. Es decir la jarra grande debe estar vacía o contener una cantidad de agua menor a la capacidad de la jarra (CJG >= 0, CJG < MJG), si esto se cumple la cantidad de agua es actualizada con la capacidad de la jarra lo que equivale a llenar la jarra (CJG1 is MJG).

En el estado posible, se definen 2 estados, esto quiere decir que hay un estado inicial y un final, se puede apreciar también que en el segundo estado cambia CJG por CJG1 dado que solo cambiará de estado la jarra grande. Además el posible estado, recibe 2 argumentos más, que son las capacidades de las jarras, dado que solo me interesa el cambio de estado de la jarra grande, se requiere saber la capacidad de dicha jarra, por tanto paso MJG y dado que no me interesa el estado de la jarra pequeña utilizo el símbolo ( _ ).

2. Otro estado posible a tomar en cuenta, es cuando se llena la jarra pequeña; y esta regla se define de la siguiente manera:



posible(estado(CJG, CJP), estado(CJG, CJP1), _ , MJP):- CJP >= 0, CJP < MJP, CJP1 is MJP.

La explicación de este predicado es similiar a lo explicado anteriromente cuando se llenó la jarra grande.

3 y 4. Los siguientes estados posibles son, cuando se vacían las jarras. Sólo se puede vaciar una de las jarras si esta contiene agua y para vaciar no se requiere saber la capacidad de las jarras.



posible(estado(CJG, CJP), estado(CJG1, CJP), _ , _ ):- CJG > 0, CJG1 is 0.
posible(estado(CJG, CJP), estado(CJG, CJP1), _ , _ ):- CJP > 0, CJP1 is 0.

5 y 6. Aún quedan 2 posibles estados más, estos son cuando se vierte el agua de la jarra grande en la pequeña y la cantidad de agua de la jarra grande es menor o mayor a la cantidad de agua faltante para llenar la jarra pequeña, esta se define así:



posible(estado(CJG, CJP), estado(CJG1, CJP1), _ , MJP):- CJG > 0, CJP < MJP, CJG =< (MJP - CJP), CJG1 is 0, CJP1 is CJP + CJG.
posible(estado(CJG, CJP),  estado(CJG1, CJP1), _ , MJP):- CJG > 0, CJP < MJP, CJG > (MJP - CJP), CJG1 is CJG - (MJP - CJP), CJP1 is MJP.

En el predicado anterior se aprecia que cambian los estados de las 2 jarras, ya que al pasar agua de una jarra hacia el otro, los dos estados se ven afectados, por eso la expresión estado(CJG, CJP), estado(CJG1, CJP1), y dado que se se pasa agua desde el recipiente grande a la pequeña es necesario saber la capacidad de la jarra pequeña (MJP), como la capacidad de la jarra grande no me interesa en estos 2 casos utilizo el símbolo ( _ ).

Al pasar agua de la jarra grande a la pequeña hay que tener en cuenta 2 posibles casos, estas son cuando la cantidad de agua a pasar es menor, igual (CJG =< (MJP - CJP)) o mayor (CJG > (MJP - CJP)) a la cantidad de agua faltante para llenar la jarra pequeña.

En el primer caso, la jarra grande queda vacía (CJG1 is 0) y la jarra pequeña queda con la cantidad de agua que ya tenía más la cantidad que se vierte desde la jarra grande (CJP1 is CJP + CJG).

En el segundo caso, la jarra grande queda con la cantidad de agua que tenía inicialmente menos la cantidad de agua faltante para llenar la jarra pequeña (CJG - (MJP - CJP)), lo cual significa que la jarra pequeña queda llena.
Todo esto se cumple si la jarra grande no esta vacía (CJG > 0).

7 y 8. Las 2 últimas reglas a definir son cuando se vierte agua de la jarra pequeña en la grande y la cantidad de agua de la jarra pequeña es menor, igual o mayor a la cantidad de agua faltante para llenar la jarra grande (similar a las reglas 5 y 6), esta se define así:



posible(estado(CJG, CJP), estado(CJG1, CJP1), MJG, _ ):- CJP > 0, CJG < MJG, CJP =< (MJG - CJG), CJP1 is 0, CJG1 is CJG + CJP .
posible(estado(CJG, CJP), estado(CJG1, CJP1), MJG, _ ):- CJP > 0, CJG < MJG, CJP > (MJG - CJG), CJP1 is CJP - (MJG - CJG), CJG1 is MJG.

La explicación de la 2 expresiones anteriores son similares a las reglas 5 y 6, con la diferencia, de que es necesario saber la capacidad del recipiente grande (MJG) para determinar la cantidad de agua faltante en dicho recipiente.

Lista de estados



miembro(X, [X | _ ]).
miembro(X, [ _ | L ]) :- miembro(X, L).

Solución

A continuación, se define la solución a este acertijo:

E = cabeza de la lista L = cola de la lista



solucion([E | L], [E | L], MJG, MJP) :- meta(E).

El predicado anterior, la solución base (definida con el mismo nombre sin acento) recibe 4 parámetros, los 2 primeros valores son listas y deben ser iguales ([E | L], [E | L]), mismas que se dividen en cabeza y cola ([E | L]), los 2 últimos valores son la capacidad de las jarras. En resúmen, hay solución, si es la meta que estoy buscando; la meta recibe la cabeza de la lista el cual es un estado y anteriormente ya se definió el hecho de la meta deseada para que sea solución meta(estado(4, _ )), en el caso que la solución base no se cumpla se define lo siguiente:



solucion([E | L], LS, MJG, MJP) :- posible(E, EP, MJG, MJP), not(miembro(EP, L)), solucion([EP, E | L], LS, MJG, MJP).

El predicado anterior define otra regla que obtiene la lista de estados posibles hasta llegar a la solución base, la solución recibe 4 valores, los 2 primero valores son listas, la primera lista es la lista de estados posibles (dividido en cabeza y cola) y la misma será almacenada en la segunda lista que es la lista solución ([E | L], LS).

En el cuerpo de la regla se verifica que a partir del último estado posible (cabeza de la lista) exista un nuevo estado posible posible(E, EP, MJG, MJP), además el nuevo estado posible no debe estar repetido en la lista de estados posibles not(miembro(EP, L)), en cuanto se cumpla estas 2 condiciones se llama una vez más al predicado solucion, pero en esta ocación se agrega el nuevo estado a la lista de estados ([EP, E | L]), esto se repetirá hasta que se encuentre la meta.

Para ejecutar el programa en SWI-Prolog, se lo hace de la siguiente manera:



solucion([estado(0, 0)], L, 5, 3).

Al predicado solución se le envía la lista de estados, va empezar solo con un elemento ([estado(0, 0)]) en la lista de estados posibles, la variable donde se almacenarán dichos estados (L) y la capacidad de la jarra grande (5) y pequeña (3) respectivamente.

La salida es la siguiente (se mostrarán varias listas de diferentes soluciones):



L = [estado(4, 0), estado(1, 3), estado(1, 0), estado(0, 1), estado(5, 1), estado(3, 3), estado(3, 0), estado(0, 3), estado(..., ...)|...] ;
L = [estado(4, 3), estado(4, 0), estado(1, 3), estado(1, 0), estado(0, 1), estado(5, 1), estado(3, 3), estado(3, 0), estado(..., ...)|...] ;
L = [estado(4, 3), estado(5, 2), estado(0, 2), estado(2, 0), estado(2, 3), estado(5, 0), estado(0, 0)] ;
...

A continuación se muestra todo el código:



meta(estado(4, _ )) .
posible(estado(CJG, CJP), estado(CJG1, CJP), MJG, _) :- CJG >= 0, CJG < MJG, CJG1 is MJG .
posible(estado(CJG, CJP), estado(CJG, CJP1), _ , MJP):- CJP >= 0, CJP < MJP, CJP1 is MJP. 
posible(estado(CJG, CJP), estado(CJG1, CJP), _ , _ ):- CJG > 0, CJG1 is 0.
posible(estado(CJG, CJP), estado(CJG, CJP1), _ , _ ):- CJP > 0, CJP1 is 0. 
posible(estado(CJG, CJP), estado(CJG1, CJP1), _ , MJP):- CJG > 0, CJP < MJP, CJG =< (MJP - CJP), CJG1 is 0, CJP1 is CJP + CJG.
posible(estado(CJG, CJP),  estado(CJG1, CJP1), _ , MJP):- CJG > 0, CJP < MJP, CJG > (MJP - CJP), CJG1 is CJG - (MJP - CJP), CJP1 is MJP. 
posible(estado(CJG, CJP), estado(CJG1, CJP1), MJG, _ ):- CJP > 0, CJG < MJG, CJP =< (MJG - CJG), CJP1 is 0, CJG1 is CJG + CJP .
posible(estado(CJG, CJP), estado(CJG1, CJP1), MJG, _ ):- CJP > 0, CJG < MJG, CJP > (MJG - CJG), CJP1 is CJP - (MJG - CJG), CJG1 is MJG. 

/*  Verifica si un elemento pertenece a una lista */
miembro(X, [X | _ ]).
miembro(X, [ _ | L ]) :- miembro(X, L). 

/*  Implementando solución */ 
solucion([E | L], [E | L], MJG, MJP) :- meta(E). 
solucion([E | L], LS, MJG, MJP) :- posible(E, EP, MJG, MJP), not(miembro(EP, L)), solucion([EP, E | L], LS, MJG, MJP).

También pueden encontrar el mismo código en GitHub.

Con esto concluimos, espero haber ayudado a entender mejor, la resolución del problema en Prolog, si tienen alguna pregunta no duden en escribirme.

¡Gracias por su lectura!

DEV Community: Fabian Quijosaca

Mandelbrot Set in JS - Smooth Scroll Zoom & Fixing Floating-Point Precision

The Problem: Everything Turns Black After ~16 Clicks

Root Cause: JavaScript Numbers Have Limited Precision

How the old zoom worked

The Fix, Part 1: Replace Click with Scroll Zoom

e.preventDefault() + { passive: false }

factor = zoomIn ? ZOOM_FACTOR : 1 / ZOOM_FACTOR

Centering on the cursor

ZOOM_FACTOR = 0.8 instead of 0.1

The Fix, Part 2: The Precision Guard

How the Renderer Still Works

Current Limitations

Future Improvements

1. Arbitrary Precision with decimal.js

2. Perturbation Theory

3. Adaptive MAX_ITERATION

4. RAF Throttle

5. Pinch-to-Zoom (Mobile)

Summary of Changes

Try It Live

Thanks for Reading

Fixing Bluetooth in Debian 9

Steps to install bluetooth driver

Bluetooth fixed!

Wrapping Up

How to wait for 2 actions to dispatch another? - Redux Saga

The shortest path - BFS

The problem

Uploading Images to AWS S3 with Serverless

1. Install AWS CLI (Command Line Interface)

2. Install the serverless framework

3. Run the following command to generate sample code with serverless.

4. Install dependencies

5. Create the function to decode the multipart/form-data

6. Function that will process and upload the images to S3

Conclusions

Plotting a binary tree in JavaScript

What is a binary tree?

Implementing the binary tree data structure

Breadth First Search

It is time to graph the tree by implementing BFS

Mandelbrot Set in JS - Zoom In

Mandelbrot set

Adding worker

Zoom In

Results

The Water Jug Riddle in JS

Implementation in JS

Mandelbrot Set in JS

Definition

Plot of the Mandelbrot Set

Next steps

Prolog: Acertijo del granjero, la cabra, el lobo y la col

Solución en Prolog

Lista de estados

Solución

Prolog: Acertijo jarras de agua

1. ¿Cuál es el problema?

2. ¿Cómo resuelvo el problema?

3. Programar solución

Lista de estados

Solución

`e.preventDefault()` + `{ passive: false }`

`factor = zoomIn ? ZOOM_FACTOR : 1 / ZOOM_FACTOR`

`ZOOM_FACTOR = 0.8` instead of `0.1`

1. Arbitrary Precision with `decimal.js`

3. Adaptive `MAX_ITERATION`