CodinGame: Derivative Time - Part 1, Recursion (Typescript)
Solution of CodinGame exercise. Simple recursion example with typescript. Formula representation inspired by lisp.
Daniel Gustaw
• 16 min read
Now we will solve exercise DERIVATIVE TIME
:
Coding Games and Programming Challenges to Code Better
Our goal is, evaluate the partial derivative of a given formula.
For instance, given the function formula “(5*(x*(y^2)))” and “y x”, the variables in respect with you must derive it
So here f(x,y) = 5xy² and you have to calculate:
d²f(x,y)
----------
dxdy
it gives you the formula 10*y. At last “x 2 y 6” means x=2, y=6, gives you the values with which you must evaluate the obtained derivative. So the answer should be 60
Note To simplify the task, only consider +, * and ^. And assume that +, * and ^ always take two arguments and that expressions are fully parenthesized.
Negative power has no parenthesis. e.g. (((18*(x^-1))+y)+z)
vars may be in other forms other than x, y, and z. Similar to identifiers in many programming languages, the var would be some letter followed by letters, numbers or underscore.
link about calculus rules:
Differentiation rules - Wikipedia](https://en.wikipedia.org/wiki/Differentiation_rules)
The rules needed here:
a'=0
(a*x)'=a
(x^a)'=a*x^(a-1) (when a is not 0)
(u+v)'=u'+v'
(u*v)'=u'*v+v'*u
Theoretical introduction to derivatives
To compute derivative of function we have to represent function as object possible to manipulate. One of possibilities is representing it as an array with operation placed on the beginning and with arguments occupying rest of positions.
This concept is intensively used in some of the languages as Lisp or Scheme. If you do not know Lisp you can easy learn it in y
minutes on page:
Learn Common Lisp in Y Minutes
So instead of write
a + b
in lisp you will write
(+ a b)
Our further solution will be heavily based on this concept of ordering. How advantages it have over a + b
? Firstly we can decompose our expressions by
const [operation, ...arguments] = expression;
Secondly for associative operations we can use reduce
function like
const res = arguments.reduce(fn, identity);
In this case identity
is value that will not change result of operation, and fn
is function assigned to operation
, eg (a,b) => a+b
for addition.
Having these basic concept in mind we can consider derivative as function that transform array representing mathematical formula to other array with other formula.
We know which transformations should be applied to addition, multiplication or powers. We also able to simplify result knowing derivatives of constant or identity function.
So lets divide our solution to four steps.
- Setup project
- Parsing input
- Evaluating values
- Computing derivative
Setup NodeJS typescript project with jest
Lets init project
npm init -y
tsc --init
in generated tsconfigl.json
we have to set
"target": "ESNext",
to be albe to use Map
or other modern data structures or syntax.
In package.json
we should set
"test": "jest"
in scripts
section and install required packages.
npm i -D @types/jest @types/node esbuild-jest jest ts-node typescript
Now lets create jest
config jest.config.ts
module.exports = {
roots: ['<rootDir>'],
testMatch: ['**/__tests__/**/*.+(ts|tsx)', '**/?(*.)+(spec|test).+(ts|tsx)'],
transform: {
'^.+\\.(ts|tsx)$': 'esbuild-jest',
},
setupFilesAfterEnv: [],
testEnvironment: 'node',
}
Finally we can create three files: lib.ts
with:
export function run(input: string): string {
return ''
}
Test test/lib.test.ts
with
import {run} from "../lib";
describe('e2e', () => {
it('temporary', () => {
expect(run('')).toEqual('')
})
});
and index.ts
that is responsible for input/output operations
import {run} from "./lib";
process.stdin.on('data', (buff) => {
const input = buff.toString();
process.stdout.write(run(input));
})
Now we should be able to run program using
echo '' | ts-node index.ts
and test by command
npm run test
Parsing Input and building objects
Lets see on input
From content of this exercise we can read that input contains 3 lines:
Line 1: formula Line 2: list of vars for partial derivative, separated by space, length of the list will be 1, 2 or 3. Line 3: vars’ values, paired and separated by space
Output is the result (always an integer).
So for example input
(5*(x*y))
x
x 2 y 6
we will have derivative by x
giving (5*y)
, that in point {x:2, y:6}
is 5*6
or simply
30
Now we will introduce three objects that will refer to these lines:
- Formula
- DiffOperator
- Coordinate
Generally any of these object should be created basing on his line. Only exception is Formula
that require variables
from coordinate
to recognize on arguments and treat them in a special way.
Now run
function from lib.ts
can be rewritten as
export function run(input: string): string {
const [F, vs, dict] = input.split('\n');
const point = new Coordinate(dict);
const diff = new DiffOperator(vs);
const formula = new Formula(F, point.variables);
return diff.actOn(formula).evaluate(point).toString();
}
What can be explained as acting derivative operator on function and evaluating it at given point. It is exactly what we need to do in this task.
Now we will implement these classes and write some tests for them
Coordinate implementation
Lets start from coordinate
export class Coordinate {
map: Map<string, number> = new Map();
constructor(input: string) {
const pairs = input.split(' ');
for (let i = 0; i < pairs.length / 2; i++) {
const [key, value] = [pairs[i * 2], Number.parseFloat(pairs[i * 2 + 1])];
this.map.set(key, value);
}
}
get variables(): string[] {
return [...this.map.keys()]
}
get(name): number {
return this.map.get(name) ?? 0;
}
}
It simply splits his string x 2 y 6
by spaces and move by pairs setting them as keys and values of internal Map
. It can return both list of keys to help in Formula
initialization and get singe value of key that is useful in evaluating.
tests for coordinate are the following
describe('coordinate', () => {
it('parsing', () => {
const point = new Coordinate('x 2 y 6');
expect(point.variables).toEqual(['x', 'y']);
expect(point.get('x')).toEqual(2);
expect(point.get('y')).toEqual(6);
expect(point.get('undefined')).toEqual(0);
})
})
Formula initialization
Next object is formula. We need two additional types
type Operator = '*' | '^' | '+' | '-';
type SubFormula = Array<string | number | SubFormula> | string | number
and can write our formula class
export class Formula {
f: SubFormula;
v: string[] = [];
}
following functions will be placed inside of this class. We need constructor that will get formula string and list of variables. To operate on string form of formula we will define two functions:
decomposeInput(input: string): SubFormula
isDecomposable(input: string): boolean
Firs will do parsing, second will check if should we expand input to elements or should we left it as atomic part of formula.
In our case we need to decompose if string starts and ends with brackets and contains operator
isDecomposable(input: string): boolean {
return input.startsWith('(') && input.endsWith(')') && /[*^+-]/.test(input)
}
Decomposition contains part that prepare three elements p
like previous, n
like next, and operator.
decomposeInput(input: string): SubFormula {
let p: SubFormula = '', operator: Operator | '' = '', n: SubFormula = '', level: number = 0;
if (!this.isDecomposable(input)) return [0];
for (let i = 1; i < input.length - 1; i++) {
if (level === 0 && !operator && /[*^+-]/.test(input[i])) {
operator = input[i] as Operator;
continue;
} else if (input[i] === '(') {
level++;
} else if (input[i] === ')') {
level--;
}
if (operator) {
n += input[i];
} else {
p += input[i];
}
}
we are using level
to determine which sub bracket level we reaching during loop.
After loop over all characters and completing p
, n
, and operator
we have to check if should we decompose or parse these elements using code
if (this.isDecomposable(p)) {
p = this.decomposeInput(p);
} else {
if (!this.v.includes(p)) {
p = Number.parseFloat(p);
}
}
if (this.isDecomposable(n)) {
n = this.decomposeInput(n);
} else {
if (!this.v.includes(n)) {
n = Number.parseFloat(n);
}
}
return [operator, p, n];
}
after defining these functions we can write constructor
constructor(input: string, variables: string[]) {
this.v = variables;
this.f = this.decomposeInput(input);
}
and test for them
describe('formula', () => {
const f = new Formula('(5*(x*y))', ['x', 'y']);
it('parse', () => {
expect(f.f).toEqual(['*', 5, ['*', 'x', 'y']]);
expect(f.v).toEqual(['x', 'y']);
});
it('parse with many brackets', () => {
const f = new Formula('((x^3)+(x^2))', ['x']);
expect(f.f).toEqual(['+', ['^', 'x', 3], ['^', 'x', 2]])
})
})
DiffOperator (derivateve) initialization
Fortunatelly derivative is super easy to construct
export class DiffOperator {
d: string[] = [];
constructor(input: string) {
this.d = input.split(' ');
}
}
inside we want to store array of variables names that we will use seqentially acting on given function.
We can skip tests for it and go to next part - Evaluating values
Evaluating values
Now we still will write code in Formula
class.
Our computing function will be able to call themself many times so to simply their interface we will split computation to:
static compute(f: SubFormula | string | number, point: Coordinate): number
and
evaluate(point: Coordinate): number
first one will be used to operate directly on SubFormula
, but second will be layer that was applied in run
in expression
diff.actOn(formula).evaluate(point)
evaluate can be defined as
evaluate(point: Coordinate): number {
return Formula.compute(this.f, point);
}
But compute
should start from classification of his argument. It can be expression, then Array.isArray(f)
will be true, number, then this number should be returned od name of coordinate, then coordinate saved in point
can be returned.
Our code will be the following
static compute(f: SubFormula | string | number, point: Coordinate): number {
if (Array.isArray(f)) {
// ... TO BE DEFINED IN NEXT STEP
} else if (typeof f === 'number') {
return f;
} else {
return point.get(f);
}
}
Most interesting is case when, f
is array. Then using theory from introduction we should decompose it to operator and arguments;
const [op, ...rest] = f;
and in next step in dependence from operator
arguments can be processed by different functions:
switch (op) {
case '+':
return <number>rest.reduce((p: number, n: SubFormula): number => p + this.compute(n, point), 0);
case '*':
return <number>rest.reduce((p: number, n: SubFormula): number => p * this.compute(n, point), 1);
case '^': {
const [p, n] = rest;
return Math.pow(this.compute(p, point), this.compute(n, point));
}
case '-': {
const [p, n] = rest;
return this.compute(p,point) - this.compute(n, point);
}
default:
return 0;
}
For associative operations like *
and +
with existing identity value we used reduce
. But for rest cases we assumed that there are two arguments and used destructuring.
To prove that it works we can add the following test to formula
section
it('evaluate', () => {
expect(f.evaluate(new Coordinate('x 1 y 2'))).toStrictEqual(10);
});
our formula defined ealier was (5*(x*y))
so we expect result 10
.
If you following all these concepts to this point, then next step will be easy logical continuation for you.
Computing derivative
Computing derivative will be done in the same style like evaluating value of function. We will split it on two methods Dynamic actOn
with interface
actOn(f: Formula): Formula
and static internal function
static derivative(s: SubFormula, dir: string): SubFormula
First one will iterate over all directions saved in d
property. Second is first order derivative in direction passed by second argument. These functions works also on other levels: actOn
will use Formula
abstraction, but derivative
need and return SubFormula
to operate on more low level structure.
We will introduce also one more static function
static simplify(s: SubFormula): SubFormula
that will not need direction and use simple algebra rules to make computation partial results more human readable and easy to process. Simplify will return the same mathematical formula but written in most simple possible manner removing unnecessary additions of 0
or multiplications by 1
.
Following functions are defined as methods of DiffOperator
.
Simplification of formula
Lets start from simplify
because of I started to explain it. To simplify formulas we will apply the folowing rules:
- all subarguments should be simplified (recursive)
- if all subarguments are numbers, they should be computed
- if one of argument is
0
or1
special treatment of second argument should be applied in dependence fromoperator
Code that implement described behavior is
static simplify(s: SubFormula): SubFormula {
if (Array.isArray(s)) {
const [op, ...rest] = s;
for (let i = 0; i < rest.length; i++) {
rest[i] = this.simplify(rest[i]);
}
if (rest.every((r) => typeof r === 'number')) {
return Formula.compute(s, new Coordinate(''));
}
if (rest[0] === 0) {
if (op === '+') return rest[1]
if (op === '*') return 0
if (op === '^') return 0
}
if (rest[0] === 1) {
if (op === '*') return rest[1]
if (op === '^') return 1
}
if (rest[1] === 0) {
if (op === '+') return rest[0]
if (op === '*') return 0
if (op === '^') return 1
}
if (rest[1] === 1) {
if (op === '*') return rest[0]
if (op === '^') return rest[0]
}
return [op, ...rest];
} else {
return s;
}
}
Derivative of formula
To define derivative of first order on given direction:
static derivative(s: SubFormula, dir: string): SubFormula
we have to assume that we can compute it on
- expression
- our variable
- constant
If it is executed on variable or constant then result will be 1
or 0
, but on expression we have to check operator
and decide which rule should we apply. This part is exactly the same concept as with evaluation, but we returns arrays with operators that represents functions instead of numbers. Code below:
static derivative(s: SubFormula, dir: string): SubFormula {
if (Array.isArray(s)) {
const [op, p, n] = s;
switch (op) {
case '*':
return ['+', ['*', p, this.derivative(n, dir)], ['*', this.derivative(p, dir), n]];
case '+':
return ['+', this.derivative(p, dir), this.derivative(n, dir)];
case '-':
return ['-', this.derivative(p, dir), this.derivative(n, dir)];
case '^': {
if (p === dir) {
if (n === 0) return 0;
return typeof n === 'number' ? ['*', n, ['^', p, n - 1]] : ['*', n, ['^', p, ['+', n, -1]]]
} else {
return 0;
}
}
}
} else if (typeof s === 'string' && s === dir) {
return 1
} else {
return 0;
}
}
we can see that only with powers there is a little confuction, because of I decided to evaluate subtraction 1
on power if it is number. I decided to skip support for a^x
because of it is exponential function that is out of scope of first part of this exercise.
Finally to implement actOn
we will need clone of formula, so on formula we should implement
clone(): Formula {
const o = new Formula('', []);
o.f = JSON.parse(JSON.stringify(this.f));
o.v = JSON.parse(JSON.stringify(this.f));
return o;
}
and then on DiffOperator
actOn(f: Formula): Formula {
const o = f.clone();
return this.d.reduce((p, n) => {
o.f = DiffOperator.simplify(DiffOperator.derivative(p.f, n));
return o;
}, o);
}
to write stable, editable and working code we should add tests
describe('diff operation', () => {
it('simplify', () => {
expect(DiffOperator.simplify(["+", ["*", 1, 0], ["*", 0, 1]])).toEqual(0);
expect(DiffOperator.simplify(['^', 'x', 1])).toEqual('x');
expect(DiffOperator.simplify(['*', 2, ['^', 'x', 1]])).toEqual(['*', 2, 'x']);
expect(DiffOperator.simplify(["*", 5, ["+", ["*", "x", 0], ["*", 1, "y"]]])).toEqual(['*', 5, 'y'])
expect(DiffOperator.simplify(["+", ["*", 5, ["+", ["*", "x", 0], ["*", 1, "y"]]], ["*", 0, ["*", "x", "y"]]])).toEqual(['*', 5, 'y'])
});
it('derivative', () => {
expect(DiffOperator.simplify(DiffOperator.derivative(['*', 2, 'x'], 'x'))).toEqual(2);
expect(DiffOperator.simplify(DiffOperator.derivative(['*', 5, ['*', 'x', 'y']], 'x'))).toEqual(['*', 5, 'y'])
})
it("a'=0", () => {
const f = new Formula('(1*1)', ['x']);
const d = new DiffOperator('x');
expect(d.actOn(f).f).toEqual(0);
});
it("(a*x)'=a", () => {
const f = new Formula('(4*x)', ['x']);
const d = new DiffOperator('x');
expect(d.actOn(f).f).toEqual(4);
});
it("(x^a)'=a*x^(a-1) (when a is not 0)", () => {
const cases = [
{in: '(x^5)', out: ['*', 5, ['^', 'x', 4]]},
{in: '(x^3)', out: ['*', 3, ['^', 'x', 2]]},
{in: '(x^2)', out: ['*', 2, 'x']},
];
for (const c of cases) {
const f = new Formula(c.in, ['x']);
const d = new DiffOperator('x');
expect(d.actOn(f).f).toEqual(c.out);
}
});
it("(u+v)'=u'+v for (x+(x^2))'", () => {
const f = new Formula('(x+(x^2))', ['x']);
const d = new DiffOperator('x');
expect(d.actOn(f).f).toEqual(['+', 1, ['*', 2, 'x']]);
});
it("(u+v)'=u'+v'", () => {
const f = new Formula('((x^3)+(x^2))', ['x']);
const d = new DiffOperator('x');
console.log("f", f);
expect(d.actOn(f).f).toEqual(['+', ['*', 3, ['^', 'x', 2]], ['*', 2, 'x']]);
});
it("(u*v)'=u'*v+v'*u", () => {
const f = new Formula('(x*x)', ['x']);
const d = new DiffOperator('x');
console.log("f", f);
expect(d.actOn(f).f).toEqual(['+', 'x', 'x']);
});
it('d(8*(y^x))/dy', () => {
const f = new Formula('(8*(y^x))', ['x', 'y']);
expect(f.f).toEqual(['*', 8, ['^', 'y', 'x']]);
expect(DiffOperator.simplify(DiffOperator.derivative(['*', 8, ['^', 'y', 'x']], 'y'))).toEqual(['*', 8, ['*', 'x', ['^', 'y', ['+', 'x', -1]]]]);
})
it('(18*(x^-1))',() => {
const f = new Formula('(18*(x^-1))', ['x']);
expect(f.f).toEqual(['*', 18, ['^', 'x', -1]]);
expect(DiffOperator.simplify(DiffOperator.derivative(f.f, 'x'))).toEqual( ['*', 18, ['*', -1, ['^', 'x', -2]]]);
});
it('d(((x^2)+(2*(z^5)))+(((18*(x^-1))+y)+z))/dx', () => {
const f = new Formula('(((x^2)+(2*(z^5)))+(((18*(x^-1))+y)+z))', ['x', 'y', 'z']);
expect(DiffOperator.simplify(DiffOperator.derivative(f.f, 'x'))).toEqual(['+', ['*', 2, 'x'], ['*', 18, ['*', -1, ['^', 'x', -2]]]]);
})
})
Finally all elements of program works so we can add also e2e
tests on run
function
describe('e2e', () => {
it('easy multiply', () => {
expect(run('(5*(x*y))\nx\nx 2 y 6')).toEqual('30')
})
it("second derivative", () => {
expect(run('(5*((x^4)*(y^2)))\nx x\nx 2 y 6')).toEqual('8640')
})
it("second derivative mix", () => {
expect(run('(5*(x*(y^2)))\ny x\nx 2 y 6')).toEqual('60')
})
it("power with number", () => {
expect(run('((x^2)+(9*(x+y)))\nx\nx 1 y 2')).toEqual('11')
})
it("power with variable", () => {
expect(run('(8*(y^x))\ny y\nx -1 y 2')).toEqual('2')
})
it("3 variables", () => {
expect(run('(((x^2)+(2*(z^5)))+((x+y)+z))\nz\nx 2 y 3 z 4')).toEqual('2561')
})
it("fraction", () => {
expect(run('(((x^2)+(2*(z^5)))+(((18*(x^-1))+y)+z))\nx\nx 3 y 4 z 1')).toEqual('4')
})
it("longer multiply", () => {
expect(run('(((x^2)*(2*(z^5)))*((x+y)+z))\nz\nx 1 y 1 z 1')).toEqual('32')
})
it("3rd derivative", () => {
expect(run('(((y^6)*(z^5))*(((3*(x^4))+y)+z))\ny y z\nx 1 y 1 z 2')).toEqual('16320')
})
it("some Greek ;)", () => {
expect(run('(((Beta^6)*(Gamma^5))*(((3*(Alpha^4))+Beta)+Gamma))\nBeta Beta Gamma\nAlpha 1 Beta 1 Gamma 2')).toEqual('16320')
})
it("maybe not xyz ;)", () => {
expect(run('(((x2^6)*(x3^5))*(((3*(x1^4))+x2)+x3))\nx2 x2 x3\nx1 1 x2 1 x3 2')).toEqual('16320')
})
it("some Vars ;)))", () => {
expect(run('(((Var_2^6)*(Var_3^5))*(((3*(Var_1^4))+Var_2)+Var_3))\nVar_2 Var_2 Var_3\nVar_1 1 Var_2 1 Var_3 2')).toEqual('16320')
})
it("bigger constants", () => {
expect(run('(50*((x^40)*(y^20)))\nx x\nx 1 y 1')).toEqual('78000')
})
it("bigger power", () => {
expect(run('(x^(y^10))\nx x\nx 1 y 2')).toEqual('1047552')
})
it("cannot find", () => {
expect(run('(5*(x*(y^2)))\nz\nx 2 y 6')).toEqual('0')
})
})
and proper github workflow
name: Node.js CI
on:
push:
branches: [ "main" ]
jobs:
build:
runs-on: ubuntu-latest
strategy:
matrix:
node-version: [14.x, 16.x, 18.x]
steps:
- uses: actions/checkout@v3
- name: Use Node.js ${{ matrix.node-version }}
uses: actions/setup-node@v3
with:
node-version: ${{ matrix.node-version }}
cache: 'npm'
- run: npm ci
- run: npm run build --if-present
- run: npm test
Further steps
In codingame there is also second part of this exercise:
Coding Games and Programming Challenges to Code Better
that will include trigonometric functions, logarithm, exponent and even the chain rule.
You can invite me to your friends on this platform using link:
https://www.codingame.com/servlet/urlinvite?u=5287657
You can find all presented code on my github:
https://github.com/gustawdaniel/codingame-derivative-time-part-1
Other articles
You can find interesting also.
Tesseract-OCR and testing selects.
We will read the content of the database table from the photo and write a few tests for database queries in Behat.
Daniel Gustaw
• 25 min read
Calculating the Difference Between JSON Files
Learn how to find missing translations in JSON files with dictionaries.
Daniel Gustaw
• 3 min read
How many families can fit on the plane - an algorithmics problem
We compare two solutions to the problem of counting free sets of adjacent seats. You will learn how to use Profiling and how much difference the use of pop and shift makes on arrays in js.
Daniel Gustaw
• 12 min read