DEV Community: Håvard Krogstie

My favourite computer science text (OR "how regex works")

Håvard Krogstie — Sat, 13 Jun 2020 14:39:41 +0000

One of my favourite things in CS is reading about algorithms not as a tutorial, but as more of a historical presentation. My favourite example is https://swtch.com/~rsc/regexp/regexp2.html,
which discusses how Nondeterministic Finite Automata modelled as virtual machine bytecode can be used instead of traditional backtracking algorithms when regex matching. All these terms are explained in the text.

The reason I like the text so much is that the algorithms are thoroughly presented and explained, with references to original papers from the 1960s by names like Rob Pike and Ken Thompson. It's nice to recognize names "in the wild", and then see examples of just what those people did. Much better than reading their Wikipedia pages imo.

And more familiar (and unfamiliar) names appear as the history is discussed. The algorithm by Thompson was used in the original Unix grep. Alfred Aho (the A in awk) is one of the authors of the infamous Dragon Book, where the technique is discussed, but without clear attribution, as several people have made DFAs and NFAs from regular expressions, without necessarily saying they do (Thompson didn't, he just made the machine code).

Aho is of course the guy from the Aho-Corasick string searching algorithm, which I randomly had to learn at some point to solve a hackerrank-task, but which I mainly remember specifically because the name Aho suddenly appeared everywhere else afterward (I had held the Dragon book, but didn't bother remembering any of the authors at first).

Anyways, the article I shared is part 2/3 of a series, which is my favourite part for reasons discussed above, but you should absolutely read the other parts if you like it.

Record fraud (find an algorithm)

Håvard Krogstie — Sat, 06 Jun 2020 12:40:33 +0000

Difficulty: Beginner

You work in a start up with very unstable finances. You have a chronological list of all income (positive integers) and expenses (negative integers), and you need to share it with investors.

However, you don't want the busines to appear unprofitable. In fact, you want it to seem as if the busines has never been in the red ever. You do this by selectively removing expenses from the list, removing as few as possible to avoid rasing suspicion.

What does the list given to the investors look like?

Input

An array of integers history

Output

An array of integers cleared where

cleared is a subsequece of hisory
sum(cleared[:n]) is non-negative for all n
len(cleared) is maximized

If multiple outputs fulfill the requirements, return any one of them

Constraints

len(history) <= 100 000

abs(history[i]) <= 10^9

Example

Input

[-3, 8, -4, -5, 4, -2, -3, -2, -2, 5, -6, 2, -5, -5]

Possible output

[8, 4, -2, -3, -2, -2, 5, 2, -5, -5]

Try to make an algorithm that's O(n log n)

Testing & things Hi Hello um what

Håvard Krogstie — Mon, 22 Jul 2019 21:34:56 +0000

Hi, I'm just testing
&

alert("Wowzers")

&

& WHa">Link: &

Watch what happens to the title when it is in a link tag

Testing & things Hi Hello um what

Håvard Krogstie ・ Jul 22 ・ 1 min read

#hiamp #howampareyou #scriptalerttestingscript

Remove terrible bus routes (find an algorithm)

Håvard Krogstie — Sat, 09 Mar 2019 15:49:09 +0000

Here is a challenge for those who want to do some algorithms programming, similar to what you would find in algorithms competitions, such as the IOI. It is not terribly difficult, but a great way to combine pen and paper solving with programming. This task uses 2D sorting, and my python solution is ~20 lines and runs in O(n*log n) time

Problem statement

You are taking the bus from A to B, sometime today. You have a list of all possible trips, with a trip being represented as the tuple (leave_time, arrive_time). The time you leave A, and the time you get to B, respectively. Both times are represented as integers.

You don't care about what the route looks like, so even really bad choices are included. There may be arbitrarily many ways of getting from A to B, some worse than others.

Turns out many of the trips are so bad that you would never want to take them. Therefore you would want to tidy up the list. Duplicates should be removed, and any trip that is objectively worse than another trip should be removed.

A trip X is objectively worse than another trip Y if X.leave_time <= Y.leave_time && X.arrive_time >= Y.arrive_time. Basically if you can leave from A later, and still arrive at B earlier, there is no point in ever taking trip X.

Given the list, write a function that returns a sorted and tidied up list.

Input

Input is read from a file or the console.
The first line contains an integer N (1 < N <= 1e5), the number of trips given.
The following N lines contain two integers leave_time and arrive_time (1 <= leave_time <= arrive_time <= 1e6), denoting a trip in the list.

Output

Output is printed out in the console or to a file.
One the first line, print the number of trips in the tidied list M.
Followed by M lines, with the integers arrive_time and leave_time for each trip in sorted order.

Sample input 1

Expected output:

Explanation

Each interval represents a possible trip. The (leave_time, arrival_time) tuple is written on the box. If the trip is objectively worse than another, the box is red, with an explanation written on it.

The routes that are left (green) are then sorted.

Sample input 2

Expected output:

If you want a solution, I will publish a commented one written in python in the comments. However, the solution is probably easier to understand if you get to it on your own.

Hi, I'm HÃ¥vard Krogstie

Håvard Krogstie — Tue, 17 Jan 2017 18:39:01 +0000

I have been coding for 8 years.

You can find me on Twitter as @HKrogstie

I live in Trondheim, Norway.

I'm still in school.

I mostly program in C++ for the time being, but only because I want a personal replacement language, and am attempting to make the compiler.

I am currently learning more about language design and compiler development.
I would love to implement my own language, but at the time being, the design changes too quickly for any compiler implementation to be made.

Also extremely happy with Emacs!

Nice to meet you.

DEV Community: Håvard Krogstie

My favourite computer science text (OR "how regex works")

Record fraud (find an algorithm)

Input

Output

Constraints

Example

Testing & things alert('Hi'); Hi Hello um what

&

Testing &amp; things Hi Hello um what

Håvard Krogstie ・ Jul 22 ・ 1 min read

Remove terrible bus routes (find an algorithm)

Problem statement

Input

Output

Sample input 1

Explanation

Sample input 2

Hi, I'm HÃ¥vard Krogstie

Testing & things Hi Hello um what

Testing & things Hi Hello um what