DEV Community: 0xc0Der

attacking the knapsack problem.

0xc0Der — Sat, 24 Aug 2024 12:14:54 +0000

The knapsack problem is a classic problem in combinatorial optimization:

The knapsack problem has been studied for more than a century, with early works dating as far back as 1897.

And the problem statement is:

Given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Sounds simple right? We just need to maximize the value of the items in the sack while keeping the weight under a certain threshold.

Turns out that it's not that easy. the problem is NP-complete, and that means that there is no known algorithm to solve it in polynomial time.

There are already algorithms out there to solve the problem, But they get exponentially slow for large inputs. Which is not very good at all.

First, the knapsack problem is in its simplest form is called 0-1 knapsack problem which is I am going to focus on.

I tried to solve it by assigning a cost to each element, But what could it be?

here I'll just go with cost = weight / value. simple but good estimate.

then add the elements to the sack form the lest cost till it hits the max capacity.

Lets look at the implementation. I've written it in JavaScript. good language for fast prototyping.

  // item[0] is item's weight
  // item[1] is item's value
  const cost = item => item[0] / item[1];

  const sorted = items => items.sort((a, b) => {
    const [ca, cb] = [cost(a), cost(b)];

    return ca == cb ? a.weight > b.weight : ca > cb;
  });

  const solve = (items, capacity) => {
    const sack = {
      items: [],
      capacity,
      weight: 0,
      value: 0
    };

    for (const item of sorted(items)) {
      if (sack.weight + item[0] <= capacity) {
        sack.items.push(item);
        sack.weight += item[0];
        sack.value += item[1];
      }
    }

    return sack;
  };

And that's it. Please let me know what you think.

Thanks for reading 😄.

Building a simple word counting parser using pari.

0xc0Der — Fri, 02 Aug 2024 10:35:22 +0000

In this post I'll implement a simple parser that counts the number of words and lines of the input.

first we need to define what we consider as a white space.

// it's written like that because
// it'll be passed to the `char` parser later.
const whitespace = ' \\r\\n\\t\\f\\v';

Then, define what is a word

a word is a sequence of non white space characters.

So, follows the definition of word and space parsers.

import { char, oneOrMore } from 'pari';

// ...

const wordChar = char(`[^${whitespace}]`);
const wsChar = char(`[${whitespace}]`);

const word = oneOrMore(wordChar);
const space = oneOrMore(wsChar);

So, how do we keep count? we need to define a parser State.

import { State, ... } from 'pari';

class CounterState extends State {
    #wordsCount = 0;
    #linesCount = 0;

    // State must have a `clone` method.
    clone() {
        const state = new CounterState(
            this.input,
            this.index,
            this.status
        );

        state.#wordsCount = this.#wordsCount;
        state.#linesCount = this.#linesCount;

        return state;
    }

    get wordsCount {
        return this.#wordsCount;
    }

    get linesCount {
        return this.#linesCount;
    }

    withIncWords() {
        this.#wordsCount += 1;
        return this;
    }

    withIncLines() {
        this.#linesCount += 1;
        return this;
    }
}

// ...

In, the space parser we need to increase the count of lines by one if we encounter a line character and increase the count of words by one at the last space (the maybe multiple consecutive spaces).

// ...

const space = oneOrMore(wsChar.ok(state => 
    state.charAt(state.index - 1) == '\n'
        ? state.withIncLines()
        : state
)).ok(state => state.withIncWords());

In the word parser we need to handle an edge case that is the end of input.

//...

const word = oneOrMore(wordChar.ok(state =>
    state.charAt(state.index) == ''
        ? state.withIncWords().WithIncLines()
        : state
));

Finally, we define out word counter parser and pass it a state with an input.

// ...
import { firstOf, ... } from 'pari';

const wc = oneOrMore(firstOf([word, space]));

const input = ...;

const result = wc.process(
    new CounterState(input)
);

// print word and line counts
console.log(
    result.wordsCount,
    'words',
    result.linesCount,
    'lines'
);

Thank you for reading 😄, If you have any questions do not hesitate to leave a comment.

functions and their inverses: 2 insightful examples.

0xc0Der — Sun, 30 Jun 2024 13:53:18 +0000

Math is often considered hard. But, that is not true. Math is about logic. Following what you know to reach an understanding of what you don't. That we can do naturally. Our brains are wired to think.

The diagnosis in my opinion to most of the problems with math is.

lack of foundation.
unwillingness to give the required mental effort.

In this series of posts, I'll try to dive a little deeper in what looks simple, But, is very foundational.

In a easy to digest #mathpills, I'll discuss fundamentals in quick pieces of elementary mathematics.

Like a logic puzzle. starting from the fundamentals you can build your way up to a very advanced an complicated structures.

So lets start with one of the most fundamental building blocks of math. functions.

basic definitions.

Let's define the function $\to B$ .

from these definitions we can find that:

any element $\in A$ its image $f (a)$ must belong to $B$
$\lbrace f(a) \mid a \in A \rbrace$ is the set of all images of elments of $A$ .

Let $\to A$ be a function that does the inverse of what $f$ does then:

f^{-1}(B) = \lbrace a \in A \mid f(a) \in B \rbrace

where

f^{-1}(x)

is a special notation to write the inverse function.

two examples.

First Example: suppose that $\subseteq A$ . does $f^{-1}(f(X)) = X$ .

To prove that these two sets are equal we must do that in two steps.

first, is $\subseteq f^{-1}(f(X))$ ?

Suppose that $\in X$ , then from the above definition $\in f(X)$ , then

\in \lbrace x \in X \mid f(x) \in f(X) \rbrace = f^{-1}(f(X))

proving that $\subseteq f^{-1}(f(X))$ .

Easy, isn't it. Just following simple definitions we were able to prove the first part, but the second will need extra assumptions to work.

is $f−1(f(x))⊆Xf^{-1}(f(x)) \subseteq X$ ?

Suppose that $\in f^{-1}(f(X))$ then $\in \lbrace x \in X \mid f(x) \in F(X) \rbrace$ , which means that $\in F(X) = \lbrace f(x) \mid x \in X \rbrace$ , then there exists $\in X$ such that $f (x) = f (a)$ .

If we can prove that $a = x$ , then $\in X$ . which proves the second part.

This is easy if $f$ is a one-to-one function.

A function is one-to-one if $∀a∈A∀b∈A(f(a)=f(b)→a=b)\forall a \in A \forall b \in A (f(a) = f(b) \rightarrow a = b)$ . which read, for any elements $\in A, b \in A$ , if have the same image, then they must be tha same.

assuming that $f$ is a one-to-one function and applying the definition above,

\rightarrow a = x

which means

\in X

proving that $f−1(f(x))⊆Xf^{-1}(f(x)) \subseteq X$ .

Second Example: suppose that $\subseteq B$ . does $f(f^{-1}(Y)) = Y$ .

Following the same procedure as the previous example.

first, is $f(f−1(Y))⊆Yf(f^{-1}(Y)) \subseteq Y$ ?

Suppose that $\in f(f^{-1}(Y))$ , there exists $\in f^{-1}(Y) = \lbrace x \in A \mid f(x) \in Y \rbrace$ such that $a = f (x)$ , then $\in Y$ .

provin that $f(f−1(Y))⊆Yf(f^{-1}(Y)) \subseteq Y$ .

For the second part, we are going to follow the logic as always, from what we know (the definitions) to what we don't (the results).

is $\subseteq f(f^{-1}(Y))$ ?

First, suppose that $\in Y$ , then, can we choose an $\in A$ such that $f (x) = a$ ? yes, if and only if the function is onto.

a function is onto if $f (A) = B$ .

In other words all the elemens in $B$ are an image of some element in $A$ .

With that property we can guarantee that our chosen element $a$ is a reverse image of some element $x$ such that $f^{-1}(a) \in f^{-1}(Y)$ .

After that, we find $\in f(f^{-1}(Y))$ . Finishing our proof.

That concludes this pill. I hope you enjoyed it. If you have any questions leave them in the comments, I'd be happy to answer them.

Thank you for reading 😄.

Building a parser combinator: the `char` parser.

0xc0Der — Tue, 25 Jun 2024 20:34:16 +0000

In the previous post, an implementation of the parser class have been introduced, and in this post will be about some basic parsers.

If the parsing process broke down to it's simplest components, a pattern will be found in these components that represent the simplest operations the parser can do, then they can be combined to form larger and more complicated patterns.

First, we need the most basic and the most important of all. a parser to match one character.

the `char` parser

It matches one character in the input string.

We need to define a parser using our Parser class from before.

const char = char =>
    new Parser(state => {
        // logic goes here
    });

Then, we need to match the current character with the given one. here I'll use Regexp to match.

const char = char =>
    new Parser(state => {
        const match = new RegExp(`^${char}$`).test(state.charAt(state.index));
    });

After that, the parser returns a new state with updated position and status.

const char = char =>
    new Parser(state => {
        const match = new RegExp(`^${char}$`).test(state.charAt(state.index));

        return state
            .withStatus(1 << (!match + !match))
            .withIndex(state.index + match);
    });

char takes a "regex" that represents one character as an input. matches the current character with it. then, returns a new state based on the result.

In the coming posts, I'll discuss what exactly is the state, and implement more complex parsers.

for the full code. take a look at

0xc0Der / pari

More than a simple parser combinator.

pari

More than a simple parser combinator.

install with `npm`.

npm i pari

usage and basic parsers

you can read the source in src/. it's self documenting and easy to read.

here is a simple overview.

import {
  char,
  firstOf,
  sequence,
  zeroOrOne,
  oneOrMore,
  zeroOrMore
} from 'pari';
// the `char` parser matches one char.
// it take a `regex` that matches exactly one char.

const digit = char('[0-9]');

// `firstOf` parser returns the first match in a list of parsers.

const lowerCase = char('[a-z]');
const digitOrLwcase = firstOf([digit, lowerCase]);

// `sequence` parser matches a list of parsers in sequence.

const hex = char('[0-9a-fA-F]');
const byteHex = sequence([char('0'), char('x'), hex, hex]

…

View on GitHub

thanks for reading 😄.

Building a parser combinator: the parser class.

0xc0Der — Wed, 05 Jan 2022 15:49:51 +0000

This series presents the implementation of a parser combinator, step-by-step from scratch explaining how it works.

first, what is a parser combinator?

a parser combinator is a higher-order function that accepts several parsers as input and returns a new parser as its output.

the parser class

This class's object represents the simplest building block of the parser combinator.

class Parser {
  constructor(process) {
    this.process = process;
  }
}

The constructor function takes a function fn = fn(state) -> state, where state is the current state of the parser, and returns a new state.

chaining parsers

The core function is to "chain" parsers, so they can work in sequence, passing the state to each other.

class Parser {
  // ...
  chain(parser) {
    return new Parser(state => {
      return parser.process(this.process(state));
    });
  }
}

The chain method takes a parser as an argument, and return a new parser.

the `next` function

To be able to do further operations on the result of a parser provided that the status of the parser matches the given status, next method have been added to take the resulting state and operates on it.

class Parser {
  // ...
  next(fn, status) {
    return this.chain(
      new Parser(state => {
        return state.status & status ? fn(state) : state;
      })
    );
  }
}

It simply "chains" a new parser to the current one, which - depending on status value - returns the state that was passed to it as it is, or the state returned from fn.

To simplify working with next, two method have been added.

operating on the `state`

The ok method works if the status is OK.

class Parser {
  // ...
  ok(fn) {
    return this.next(fn, State.OK);
  }
}

catching errors

The error method works if there was an error.

class Parser {
  // ...
  error(fn) {
    return this.next(fn, State.ERROR);
  }
}

Well, that that doesn't look very useful right now, but in the next post, basic parsers will be implemented using the parser class, and finally they can be "combined" together to make larger parsers.

You can find the full code on github on main branch

0xc0Der / pari

More than a simple parser combinator.

pari

More than a simple parser combinator.

install with `npm`.

npm i pari

usage and basic parsers

you can read the source in src/. it's self documenting and easy to read.

here is a simple overview.

import {
  char,
  firstOf,
  sequence,
  zeroOrOne,
  oneOrMore,
  zeroOrMore
} from 'pari';
// the `char` parser matches one char.
// it take a `regex` that matches exactly one char.

const digit = char('[0-9]');

// `firstOf` parser returns the first match in a list of parsers.

const lowerCase = char('[a-z]');
const digitOrLwcase = firstOf([digit, lowerCase]);

// `sequence` parser matches a list of parsers in sequence.

const hex = char('[0-9a-fA-F]');
const byteHex = sequence([char('0'), char('x'), hex, hex]

…

View on GitHub

Thanks for reading 😄.

DEV Community: 0xc0Der

attacking the knapsack problem.

Building a simple word counting parser using pari.

functions and their inverses: 2 insightful examples.

basic definitions.

two examples.

Building a parser combinator: the `char` parser.

the char parser

0xc0Der / pari

More than a simple parser combinator.

pari

install with npm.

usage and basic parsers

Building a parser combinator: the parser class.

the parser class

chaining parsers

the next function

operating on the state

catching errors

0xc0Der / pari

More than a simple parser combinator.

pari

install with npm.

usage and basic parsers

the `char` parser

install with `npm`.

the `next` function

operating on the `state`

install with `npm`.