Maximum Inequality [Linear Search] rust and typescript
Simple hackeartch task solved in node js and rust. You con compare these two languages on example of this problem. I recommend to solve it independently before reading solutions.
Daniel Gustaw
• 6 min read
Problem
A function on a binary string T of length M is defined as follows:
F(T) = number of indicesi (1≤i<M) such that Ti≠Ti+1.
You are given a binary string Sof length N. You have to divide string S into two subsequencesS1,S2 such that:
- Each character of string S belongs to one of S1 and S2.
- The characters of S1and S2.must occur in the order they appear in S.
Find the maximum possible value of F(S1)+F(S2).
**NOTE:**A binary string is a string that consists of characters `0` and `1`. One of the strings S1, S2 can be empty.
Input format
- The first line contains Tdenotingthe numberof test cases. The description of T test cases is as follows:
- For each test case:
- The first line contains Ndenoting the size of string S.
- The second line contains the string S.
Output format For each test case, print the maximum possible value of F(S1)+F(S2) in a separate line.
Constraints
1≤T≤10^5
1≤N≤10^5
∣S∣=N $$
S contains characters ′0′ and ′1′.
Sum of N over all test cases does not exceed 2 â‹… 10^5.
Sample Input
3
3
011
4
1100
5
11111
Sample Output
1
2
0
Explanation
The first test case
- One possible division is S1=011,S2="" (empty string). Here F(S1)+F(S2)=1+0=1. There is no way to divide the given string to obtain a greater answer.
The second test case
- The optimal division is S1=10,S2=10. Here F(S1)+F(S2)=1+1=2. There is no way to divide the given string to obtain a greater answer.
The third test case
- For any possible division of S, F(S1)+F(S2)=0.
Solution
I will describe method and then present code in javascript and rust.
Method
To solve this problem we can create two pointers - one for any head of subsequence. Then we changing first sequence value as soon as possible. In other case we changing second. Any change should increment counter of changes. This simple algorithm has O(n) complexity.
Node JS Solution
In node
solution we will use readline
module. It allow to create interface which throws events connected with reading from standard input.
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
terminal: false
});
We will be able to add event listeners on rl
object but now lets create input_array
which will be filled by subsequent lines.
const input_array:string[] = []
Now we can listen on any added line in standard input, and append them to this array.
rl.on('line', (line: string) => {
input_array.push(line);
});
When input will be closed then We want to build output and pass it to standard output:
rl.once('close', () => {
let index = 0;
let T = parseInt(input_array[index++].trim(), 10);
for (let t_i = 0; t_i < T; t_i++) {
let N = parseInt(input_array[index++].trim(), 10);
let S = input_array[index++].trim();
let out_ = solve(N, S);
rl.output.write(out_.toString());
rl.output.write('\n');
}
process.exit();
});
we are using there solve
function that will find maximum number of changes in both. So there is implementation of solve
function.
function solve(N: number, S: string) {
let s1: string = '';
let s2: string = '';
let changes = 0;
for (let i=0; i<N; i++) {
const v = S[i];
if (!s1) {
s1 = v;
} else if (!s2 && v === s1) {
s2 = v;
} else if (s1 !== v) {
s1 = v;
changes++;
} else if (s2 && s2 !== v) {
s2 = v;
changes++;
}
}
return changes;
}
This is end of typescript, but worth to present test. We will not use jest
, ava
or mocha
that are designed to test code internally. Instead I decided to test program by blackbox test written in shunit2
. There is text
file with test data
3
3
011
4
1100
5
11111
From exercise content we know that solutions are 1
,2
and 0
. So my test is written in equality_test.sh
#! /bin/sh
testEquality() {
RES=$(cat < text | ts-node index.ts)
EXP=$(printf "1\n2\n0")
assertEquals "${EXP}" "${RES}"
}
# Load shUnit2.
. /usr/share/shunit2/shunit2
Finally github action workflow
name: Node.js CI
on:
push:
branches: [ "main" ]
paths: [ "node" ]
env:
working-directory: ./node
jobs:
build:
runs-on: ubuntu-latest
defaults:
run:
working-directory: ${{ env.working-directory }}
strategy:
matrix:
node-version: [14.x, 16.x, 18.x]
steps:
- uses: actions/checkout@v3
- name: Install shunit
run: sudo apt install -y shunit2
- name: Use Node.js ${{ matrix.node-version }}
uses: actions/setup-node@v3
with:
node-version: ${{ matrix.node-version }}
cache: 'npm'
cache-dependency-path: ${{ env.working-directory }}/package-lock.json
- run: npm ci
- run: npm install -g ts-node
- run: npm run build --if-present
- run: npm test
Rust Solution
In rust we divided project to 2 files. Almost empty main.rs
use linear_search_max_inequality::max_inequality;
use std::io;
fn main() -> io::Result<()>{
max_inequality(&mut io::stdin(), &mut io::stdout())
}
and lib.rs
with all logics and unit tests. Lets start from tests
use std::io::{Write, Read, Error};
use std::fmt::{Display, Formatter};
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn printing_in_new_lines_test() {
let vec = NumVec(vec![0,1,2]);
assert_eq!(format!("{}", vec), "0\n1\n2");
}
#[test]
fn test_of_single_series_001_test() {
let res = compute_max_inequality(3, "001");
assert_eq!(res, 1);
}
#[test]
fn test_of_single_series_1100_test() {
let res = compute_max_inequality(4, "1100");
assert_eq!(res, 2);
}
#[test]
fn test_of_single_series_11111_test() {
let res = compute_max_inequality(5, "11111");
assert_eq!(res, 0);
}
#[test]
fn string_new_test() {
let s1 = String::new();
assert_eq!(s1, "".to_string());
}
#[test]
fn max_inequality_001_test() {
let mut out: Vec<u8> = Vec::new();
max_inequality(&mut "1
3
001".as_bytes(), &mut out).unwrap();
assert_eq!(out, b"1\n");
}
}
Reading tests we can see that there is function compute_max_inequality
that solving main problem and max_inequality
to handle input and output properly.
Solving problem is generally copy from node solution with a little complications from necessity of conversion chars to strings.
fn compute_max_inequality(_length: u32, series: &str) -> u32 {
let mut s1:String = String::new();
let mut s2:String = String::new();
let mut changes = 0u32;
for c in series.chars() {
let v = c.to_string();
if s1 == "" {
s1 = v;
} else if s2 == "" && s1 == v {
s2 = v
} else if s1 != v {
s1 = v;
changes+=1;
} else if s2 != "" && s2 != v {
s2 = v;
changes+=1;
}
}
changes
}
other problem that was typical only for rust is a little overengineered printing vector to new lines
struct NumVec(Vec<u32>);
impl Display for NumVec {
fn fmt(&self, f: &mut Formatter) -> Result<(), std::fmt::Error> {
let mut out = String::new();
for num in &self.0[0..self.0.len() - 1] {
out.push_str(&num.to_string());
out.push_str("\n");
}
out.push_str(&self.0[self.0.len() - 1].to_string());
write!(f, "{}", out)
}
}
Finally main function that read lines and compute results.
pub fn max_inequality(
input: &mut impl Read,
output: &mut impl Write,
) -> Result<(), Error> {
let mut buffer = "".to_string();
input.read_to_string(&mut buffer)?;
let mut iterator = buffer.split("\n");
iterator.next();
let mut results:Vec<u32> = vec![];
while let Some(length) = iterator.next() {
let length: u32 = length.parse().unwrap();
let series = if let Some(series) = iterator.next() { series } else { "" };
results.push(compute_max_inequality(length, series));
}
let out = format!("{}\n", NumVec(results));
output.write_all(out.as_bytes())?;
Ok(())
}
Rust workflow in github is pretty standard
name: Rust
on:
push:
branches: [ "main" ]
paths: [ "rust" ]
env:
CARGO_TERM_COLOR: always
working-directory: ./rust
jobs:
build:
runs-on: ubuntu-latest
steps:
- uses: actions/checkout@v3
- name: Build
run: cargo build --verbose
working-directory: ${{ env.working-directory }}
test:
runs-on: ubuntu-latest
steps:
- uses: actions/checkout@v3
- name: Run tests
run: cargo test --verbose
working-directory: ${{ env.working-directory }}
Other articles
You can find interesting also.
How the war for compatibility shaped the frontend?
We describe how deprecation and maintaining backward compatibility have influenced the direction of web technology development.
Daniel Gustaw
• 5 min read
Scraping from money.pl in 30 lines of code.
See a simple case study of downloading and processing data from a paginated table.
Daniel Gustaw
• 8 min read
Data logging in MySql, Ajax, and Behat
We will write a simple web application - a calculator. Using it as an example, we will show how to configure selenium with behat and perform automated tests on it.
Daniel Gustaw
• 14 min read