I recently finished watching a tremendous free distributed systems course. The lecturer is a famous Dr. Martin Kleppmann who wrote a well-known book with the red wild boar cover 😄

This course includes 8 lectures split into 23 videos:

1. Introduction
2. Models of distributed systems
3. Time, clocks, and ordering of events
4. Broadcast protocols and logical time
5. Replication
6. Consensus
7. Replica consistency
8. Case studies

Martin made a great introduction to distributed systems. He starts with basic concepts and terms definition. Martin explains why it's important to understand how these systems work nowadays and where they're used.

Then, he switches to the main issues related to distributed systems and describes 2 problems:

• The two generals problem
• The Byzantine generals problem

Martin also explains what the system model is and how it's related to faults that can occur. The distributed systems algorithms help to deal with it. He came to the conclusion for distributed systems we need to pick one statement from each part:

1. Network: reliable, fair-loss, or arbitrary
2. Nodes: crash-stop, crash-recovery, or Byzantine
3. Timing: synchronous, partially synchronous, or asynchronous

In the "Time, clocks, and ordering of events" lecture, Martin explains the monotonic clocks and the clock synchronization process. He also shows why we cannot rely on the physical clock in distributed systems.  

The "Broadcast protocols and logical time" lecture is about the difference between physical and logical clocks (Lamport and Vector clocks), and broadcast algorithms (FIFO broadcast, Causal broadcast, Total order broadcast, and FIFO-total order broadcast).

The 5th lecture explains "Replication". Martin shows what idempotency means in distributed systems and how to make the system idempotent. He also describes the quorum and replication mechanism.

The next part is all about "Consensus" and related algorithms.

The two best-known consensus algorithms are Paxos and Raft. In its original formulation, Paxos provides only consensus on a single value, and the MultiPaxos algorithm is a generalisation of Paxos that provides FIFO-total order broadcast. On the other hand, Raft is designed to provide FIFO-total order broadcast “out of the box”.

The "Replica consistency" chapter explains the two-phase commit (2PC), linearizability,  and eventual consistency model. Martin explains related algorithms and limitations based on the CAP theorem.

The last part ("Case studies") is important because it shows real examples of distributed systems and how they deal with mentioned issues.  Martin describes the conflict-free replicated data types (CRDTs) that help to manage the case when several concurrent writes to the same object need to be integrated into a single final state. He also shows the logic that stays behind Google’s Spanner database.

Summary

It's a definitive lore gem. Martin explains everything in detail so everyone can understand the major algorithms and rules that stay behind distributed systems.
Of course, it's not so easy to remember all of these concepts, but after finishing the course you will get a good understanding of distributed systems and how they work. You also can always return back and refresh your knowledge if it's needed. The great thing is this knowledge (as well as Martin's most popular book) is fundamental. Thanks, Martin for making it publicly available ❤️!

Lecture videos: https://www.youtube.com/playlist?list=PLeKd45zvjcDFUEv_ohr_HdUFe97RItdiB
Coursebook: https://www.cl.cam.ac.uk/teaching/2122/ConcDisSys/dist-sys-notes.pdf

P.S. Interestingly Martin recommends reading the  “Distributed Systems” book by van Steen & Tanenbaum. That's something I'm currently into. I started participating in a "Code of Architecture" book reading class organized by an architecture team of one of the biggest tech banks. They run a weekly call with some guests or internal architects where they discuss a particular chapter from the book they're currently reading. Alexander Polomodov (Director of their digital ecosystem development department) also has a tech blog on Medium where he publishes his book reviews. As for me, it's a great format that helps me to keep reading pace and to be a motivated learner. It also allows me to understand better the book material based on real examples and discussions.

I recently finished reading the book I've heard a lot of. Both authors are well-known Software Architects with dozen years of experience. Mark Richards, for example, runs great bi-weekly Software Architecture Monday lessons.
I want to share my opinion about this book, save some notes I made, and explain why I think it is worth to be read.

The book is well-structured and it has 3 main parts:

1. Foundations
2. Architecture Styles
3. Techniques and Soft Skills

Foundations

Authors start with the definition of software architecture and Architecture role. They says the architecture consists of several things:

1. Structure
2. Architecture Characteristics
3. Architecture Decisions
4. Design Priciples  

The architecture structure describes the system based on the used architecture styles.

The architecture characteristics of the system are the same as the nonfunctional requirements. Architects can use them for describing architecture structures and being able to compare different design decisions and approaches.
Here's the list of some architecture characteristics.

The architecture decisions define the rules for how a system should be constructed. It's based on architecture characteristics the system should provide.

The design principles behave like a guideline. They are more recommendations than strict rules engineers should follow in order to build the desired system.

Authors also define the expectations of an architect. They highlight and describe 8 core expectations:

1. Make architecture decisions
2. Continually analyze the architecture
3. Keep current with the latest trends
4. Ensure compliance with decisions
5. Diverse exposure and experience
6. Have business domain knowledge
7. Possess interpersonal skills
8. Understand and navigate politics

Two important software architecture statements are mentioned:

Everything in software architecture is a trade-off.
– First Law of Software Architecture

Why is more important than how.
– Second Law of Software Architecture

A good software architect should also have architectural thinking (thanks captain obvious 🙂). So authors say it's based on analyzing trade-offs and understanding business drivers skills.

Then, they focus on modularity. It's mentioned how to measure modularity by using cohesion, coupling, and connascence. Authors use specific formulas that help to calculate these metrics.

Several next chapters are related to architecture characteristics:

• definition of architecture characteristics: operational, structural, and cross-cutting;
• identification of architecture characteristics: explicit and implicit;
• measuring and governing architecture characteristics: operational and structural measures + fitnes functions;
• scope of architecture characteristics.

All this information is extended by architecture katas and decisions based on architecture characteristics. It's useful to see how the theoretical information can be applied to real-world examples.

When we understand architecture characteristics it is time to return back to the modularity and discuss the component-based thinking.

Components can be presented as:

1. Libraries: wrappers, that communicate via language function call mechanism.
2. Services: run in its own address space, communicate via different protocols (HTTP, TCP/IP, etc..), and form standalone units.

Components can be grouped by using 2 approaches:

1. Technical partitioning (layered architecture).
2. Domain partitioning (service architecture).

Authors describe how to identify components, analyze their roles and characteristics.

There're 3 main components discovering approaches:

• Actor/Actions approach: map requirements to components (what they can do and perform).
• Event storming: comes from DDD and based on an assumption the system will use messages/events as a communication channel.
• Workflow approach: it's similar to the event storming approach but without the constraints to use the message-based channel.

When the foundation is covered, it's time to understand architecture styles that exist nowadays.

Architecture Styles

This part authors start with the differences between monolithic (single deployment unit of all code) and distributed (multiple deployment units connected through remote access protocols) systems.

Monolithic architectures can be:

1. Layered
2. Pipeline
3. Microkernel

Distributed architectures include:

1. Sevice-based
2. Event-driven
3. Space-based
4. Service-oriented
5. Microservices

It's said that distributed architecture styles have multiple advantages but they also have plenty of difficulties or fallacies.
Here's the image of the list of 8 fallacies of distributed systems I took from a great technical blog.

All of these fallacies are quite obvious but engineers often don't take them into account when they build distributed systems.

Then authors describe 8 architecture styles with the topology, diagrams, and good examples:

1. Layered architecture: a style with several isolation levels, e.g. presentation layer, business layer, services layer, persistence layer, database layer.
   Examples: a standard frontend, backend, and database isolation inside a single monolith.
2. Pipeline architecture: it came from Unix systems where functionality is split into discrete parts that can communicate with each other via pipes.
   Examples: ETL tools, Apache Camel.
3. Microkernel architecture: it includes a core system and plug-in components.
   Examples: Eclipse IDE, Jira, Jenkins.
4. Service-Based architecture: independent applications that are deployed separately but usually have a single database.
5. Event-Driven architecture: it's made up of decoupled event processing components that asynchronously receive and process events. There are 2 topology types: mediator (a single node that is responsible for all communications between other nodes) and broker (there's no central place that manages all the messages).
6. Space-based architecture: it's based on processing units that can have a shared database but should also include replicated local storages (caches).
7. Orchestration-Driven Service Oriented architecture: it uses shared resources and communication buses across multiple services. It sounds more like an enterprise legacy.
8. Microservices architecture: it includes multiple services for each bounded context. Each service is independant and include its own persistance layer (database). The communication between services can use the choreography or the orchestration approach (similar to the Event-Driver architecture style).

When the main architecture styles are described, it's time to see how to choose the correct one for a particular system. Authors mention the evaluation approach that allows architecture to build systems based on:

• Observations from the past
• Changes in the ecosystem
• New capabilities
• Acceleration
• Domain changes
• Technology changes
• External factors

In order to compare these styles, authors use a set of architecture characteristics. I created a summary table with all the described architecture styles.

The main point here is (again):

Everything is a trade-off.

However, knowing all these styles doesn't automatically make you an architect. You also need...

Techniques and Soft Skills

In the last part of this book authors cover other important topics:

• decision justification;
• documentation;
• communication.

They describe the architecture decision anti-patterns:

1. Covering your assets: avoiding making the decision out of fear of making the wrong choice.  
   Solution: wait until the last responsible moment
2. Groundhog day: it happens when people don't understand why this decision has been made and constantly asking about the reasons.
   Solution: provide clear technical and business justifications.
3. Email-drivern architecture: it happens when there is no central place where the architecture decisions are stored.
   Solution: keep architecture decision records (ADR) in a single point of truth, e.g. git repo.

Then, authors explain the structure of architecture decision records (ADR) and request for comments (RFC).

Possible ADR's structure:

• title;
• status;
• context;
• decision;
• consequences;
• compliance;
• notes.

The interesting chapter in this part is related to the architecture risk analyze.
It's shown how to use the risk matrix and risk assessment.

When leveraging the risk matrix to qualify the risk, consider the impact dimension first and the likelihood dimension second.

For example, what is the impact if one of the services goes down and becomes unavailable? Let's say, it'll be an issue and the system won't be able to work without this service. So, the impact is high (3). However, let's assume, this service is situated in a highly available server or there's a cluster of these services. In that case, the potential risk is low(1). It gives us an overall risk rating of 3 (medium).

A risk assessment is a summarized report of the overall risk. It's based on analysis of every system element and its risk criteria by using the risk matrix.

The authors also say it's better to include as many senior engineers, team leaders, and architects in this analysis. This procedure is called risk storming (don't mess it with the event storming).

Then authors make a quick note about the tools, standards, and techniques that can be used for diagramming and making presentations: UML, C4, ArchiMate.

The effective architect should also apply the correct level of control and understand plenty of external factors:

• team size;
• team familiarity;
• team experience;
• project complexity;
• project duration.

And last but not least, soft skills play a huge role in an architect's career. Negotiation skills are important as well as the 4 C's of architecture: Communication, Conciseness, Collaboration, and Clarity.

Architects should know so many things and constantly track new technologies. But how to do that in our busy lives? The authors propose to use the 20-minutes rule: spend this time learning something new every morning just before starting your job routine. One possible way is to build the personal technology radar.

Summary

The book is well-structured and gives a high-level overview of modern software architecture design practices and styles. I'd recommend it to any Engineer who wants to better understand the responsibilities of the Software Architecture role as well as the main difficulties Architects need to deal with.

I'll definitely keep this book on my bookshelf and return to it from time to time. It tells a lot to me 👍.

That's it! Theoretical knowledge is good but don't forget that:

Practice is the proven way to build skills and become better at anything in life...including architecture.
– Mark Richards & Neal Ford

P.S. The newest book of these authors  "Software Architecture: The Hard Parts" is already on my reading list for 2023 and I can't wait to start learning it.

2022 was a really tough year so I read only 11 books 😞

This year (2023) I decided to create a reading plan in advance and track my progress every week.

This list includes nonfiction, sci-fi, classics, and tech books. All of them were recommended by my friends or other great people. Some of these books I've already read but I want to re-read them for better understanding concepts and ideas that stay behind them.

It is a dynamic and unsorted list. It can be changed during the year but it should help me to keep the reading pace at least (or I hope so 😄).

Reading list

Building Evolutionary Architectures by Neal Ford, Rebecca Parsons, Patrick Kua, Pramod Sadalage

Software Architecture: The Hard Parts by Neal Ford, Mark Richards, Pramod Sadalage, Zhamak Dehghani

Distributed systems for fun and profit by Mikito Takada

Distributed Systems by M. van Steen and A.S. Tanenbaum

Cryptonomicon by Neal Stephenson

A Man Called Ove by Fredrik Backman

The Inner Game of Tennis: The Classic Guide to the Mental Side of Peak Performance by W. Timothy Gallwey

Life 3.0: Being Human in the Age of Artificial Intelligence by Max Tegmark

Entertaining Greece. Stories of Ancient Greek Culture by Mikhail Gasparov

The Millionaire Next Door: The Surprising Secrets of America's Wealthy by Thomas J. Stanley and William D. Danko

The Empire Must Die: Russia's Revolutionary Collapse, 1900-1917 by Mikhail Zygar

A Brief History of Everything by Ken Wilber

The Beginning of Infinity: Explanations That Transform the World by David Deutsch

How To Be A Stoic: Ancient Wisdom for Modern Living by Massimo Pigliucci

Behave: The bestselling exploration of why humans behave as they do by Robert M Sapolsky

12 Rules for Life: An Antidote to Chaos by Jordan B. Peterson

How the World Really Works: The Science Behind How We Got Here and Where We're Going by Vaclav Smil

The Intelligent Asset Allocator: How to Build Your Portfolio to Maximize Returns and Minimize Risk by William J. J. Bernstein

The Fabric of Reality by David Deutsch

The Psychology of Money: Timeless lessons on wealth, greed, and happiness by Morgan Housel

The Longevity Diet: Slow Aging, Fight Disease, Optimize Weight by Valter Longo

Thinking, Fast and Slow by Daniel Kahneman

I'm Dmitry, a Software Engineer with an entrepreneurial mindset.
I'm going to share here my thoughts, plans, ideas, and everything I'll find interesting.

Stay tuned!

Here is an excellent resource with the Big-O cheat sheet.

Hi! As I mentioned earlier, I decided to recall some fundamental knowledge.
In this article, I'd like to share with you the difference between sorting algorithms. I know, that it can be very simple, but how many times do you think about it? We all use it very often (for example, the sort method in ruby), but not everyone takes a look under the hood.

So, here I want to describe the most popular sorting algorithms (again 🙂).

Selection Sort

Selection sort is an algorithm that is based on scanning an array from left to right.
It means:

a) None entries situated on the right part of the sorted data are smaller than any entries from the left part
b) The left-side entries of the sorted data part are in ascending order

So, we start from the first element of the data with the index i and go through the data from left to right. If we find the smaller element, we need to change it with an element with an index i. In the next iteration, we move the pointer (index i) to the right by 1 and repeat searching smaller elements from the right part of the data.

The time complexity of the algorithm is O(n2).

Insertion Sort

Insertion sort is another simple sorting algorithm.
The main steps are:

a) Split the data into 2 parts: sorted and unsorted
b) Start from the first element of the data with the index i and put it into the sorted part
c) Increment the index i by 1, and select the next element
d) Find a new index for the selected element. Go through the sorted part of the data from right to left unless a smaller element is found
e) Insert the selected element into the sorted part of the data using a new index
f) Go to c until the data is sorted

The time complexity of this algorithm is the same as for the selection sort: O(n2)

Shellsort

The shellsort  algorithm is an improved version of the insertion sort.
This method is based on sorting pairs of elements that are situated far apart from each other.
Shellsort splits data into some parts using an interval. This interval is calculated by the formula that was introduced by Shell:

d = f l o o r ( g a p / 2 )
where the gap — is an interval with the initial value N (count of elements).

The main steps of this algorithm are:

a) Initialize the value of d
b) Divide the list into smaller sublists using an interval h
c) Sort these sublists using the insertion sort algorithm
d) Repeat until the complete list is sorted

The time complexity of the algorithm depends on the interval d.
In the worst case: O(n2).
In the best case: O(n∗log(n)).

Mergesort

Mergesort is one of the divide-and-conquer algorithms which is built on top of recursion.
Conceptually, the merge sort works as follows:

a) Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered as a sorted one).
b) Repeatedly merge sublists to produce new sorted sublists until there is only 1 remaining sublist. This will be the sorted list.

The time complexity of the algorithm in the worst case is O(n∗log(n)).

Quicksort

The quick sort algorithm is a highly efficient algorithm that is also recursion-based.

The steps of the algorithm are:

a) Pick an element (pivot) from the initial array.
b) Partitioning: reorder the array so all elements with values less than the pivot will be placed before the pivot, while all the elements with values greater than the pivot will be placed after it (equal values can go either way).
After this partitioning, the pivot is in its final position. This is called the partition operation.
c) Recursively apply the above steps to the sub-array of elements with smaller values and to the sub-array of elements with greater values.

The quicksort’s divide-and-conquer  technique makes this algorithm a great parallel execution candidate.

The time complexity of the algorithm depends on pivot element and can be:

In the worst case: O(n2)
In the best case: O(n∗log(n))

Summary

For small data sets, it is better to use the selection sort or insertion sort algorithms.
For other cases, it is better to prefer O(n∗log(n))algorithms.

Bonus: here is a great data structures and algorithms tutorial.

It’s always interesting to learn something new, especially if it’s fundamental knowledge.

Recently I have found a very interesting course about algorithms. Lectures are meaningful and practical. I recommend them to everyone who wants to understand basic algorithms.
All algorithms are implemented in Java, but I decided to write them in Ruby too. In my view, it doesn’t matter what language you choose in this case. The main goal is to better understand these algorithms.
So, in this post, I want to tell you about Union-Find (UF) algorithms.

Dynamic connectivity

Firstly, we should understand the reason of this type of algorithm. Just have a look at the picture:

As you can see, there are 2 points: p and q. Question: is there a path between p and q?
Not so easy to answer, right? 🙂

This type of problem is called the connectivity problem. Wikipedia says:

In computing and graph theory, a dynamic connectivity structure is a data structure that dynamically maintains information about the connected components of a graph.

So, dynamic connectivity is a data structure, which can be used for describing a graph. But, what does it mean? How can we use it for answering the question?
It means, we can describe the way from p to q through the graph of elements. Each element is a point, which can be connected with another one. For example, let’s say we have 10 objects and they are separated initially (they are independent components):

We can connect and check if some of them are already connected. The connection action is called union. TheFind is an operation that checks if two objects are in the same component. So, we can union 4 with 3:

Here are more connectivity examples:

Now, we know what is the dynamic connectivity, but how can we implement it? There are some algorithms to do Union-Find operations.

Quick-Find

The Quick Find is the easiest UF algorithm.

class QuickFind
  def initialize(size)
    @ids = (0..size-1).to_a
  end

  def find(index)
    @ids[index]
  end

  def connected?(p, q)
    find(p) == find(q)
  end

  def union(p, q)
    return if connected?(p, q)

    old = @ids[p]
    new = @ids[q]

    @ids.map! { |val| val = (val == old)? new : val }
  end

  def count
    @ids.uniq.size
  end
end

The find operation just checks whether p and q are in the same component (have the same value). The union operation changes all entries with @ids[p] to @ids[q]

Quick-Union

The Quick-Union is a more complex algorithm.

class QuickUnion
  attr_reader :count

  def initialize(size)
    @ids = (0..size-1).to_a
    @count = size
  end

  def find(index)
    @ids[index] == index ? index : find(@ids[index])
  end

  def connected?(p, q)
    find(p) == find(q)
  end

  def union(p, q)
    return if connected?(p, q)

    @ids[find(p)] = find(q)
    @count -= 1
  end
end

The find operation checks if p and q have the same root. The union operation changes the id of p’s root to the id of q’s root.

In that case, the find operation is more complicated, then the union one. Finding the root means passing all paths through the graph from a particular element to its root. A tree of components can be very deep in that case. In other words, we can union very tall trees, which require a lot of find operations. That is why this algorithm can be improved by checking the order of the joined objects.

Weighted Quick-Union

It’s an improved version of the Quick-Union algorithm.

class WeightedQuickUnion
  attr_reader :count

  def initialize(size)
    @ids = (0..size-1).to_a
    @size = Array.new(size, 1)
    @count = size
  end

  def find(index)
    @ids[index] == index ? index : find(@ids[index])
  end

  def connected?(p, q)
    find(p) == find(q)
  end

  def union(p, q)
    return if connected?(p, q)

    root_p, root_q = find(p), find(q)
    bigger?(root_p, root_q) ? join(root_q, root_p) : join(root_p, root_q)

    @count -= 1
  end

  private

  def bigger?(root_1, root_2)
    @size[root_1] > @size[root_2]
  end

  def join(root_1, root_2)
    @ids[root_1] = root_2
    @size[root_2] += @size[root_1]
  end
end

As you can see, we have an array (@size), which includes the sizes of all components. The union method checks the size of components and joins smaller ones with bigger ones. It means fewer find operations are required. Thus, the order is important.

However, we can make it even better!

Weighted Quick-Union With Path Compression

Every time when we go through the tree (after computing the root of p), we can make the id of each examined node point to that root.
For example, we have the tree:

After running the find operation, the tree will be changed to:

All we need is just change a few lines of our find method.

def find(index)
  return index if @ids[index] == index

  @ids[index] = @ids[@ids[index]]
  find(@ids[index])
end

Well, it is time to test it!

Tests

I  found some data sets. One of them includes 11 union operations, and another one 900.

class Benchmarks
  def tiny
    test File.read('./tiny_UF.txt')
  end

  def medium
    test File.read('./medium_UF.txt')
  end

  private
  def test(str)
    data = str.split("\n")
    size, pairs = data.shift, data

    Benchmark.bm(20) do |bm|
      %w(QuickFind QuickUnion WeightedQuickUnion WeightedQuickUnionPC).each do |uf_class|
        bm.report(uf_class) do
          uf = Object.const_get(uf_class).new size.to_i
          union(uf, pairs)
        end
      end
    end
  end

  def union(uf, pairs)
    pairs.each do |pair|
      p, q = pair.split(' ')
      uf.union(p.to_i, q.to_i)
    end
  end
end

# tiny data set
  user       system     total     real
QuickFind
  0.000000   0.000000   0.000000 (0.002838)
QuickUnion
  0.000000   0.000000   0.000000 (0.000091)
WeightedQuickUnion
  0.000000   0.000000   0.000000 (0.000078)
WeightedQuickUnionPC
  0.000000   0.000000   0.000000 (0.000056)

# medium data set
  user       system     total     real
QuickFind
  0.060000   0.010000   0.070000 (0.051383)
QuickUnion
  0.010000   0.000000   0.010000 (0.002796)
WeightedQuickUnion
  0.000000   0.000000   0.000000 (0.001658)
WeightedQuickUnionPC
  0.010000   0.000000   0.010000 (0.001589)

As you can see, everything works as we expected and Weighted Quick-Union With Path Compression is the quickest algorithm.

Here's the Union-Find algorithms performance comparison:

Conclusion

Union-Find algorithms are widely used. We can see them in different applications:

• Dynamic connectivity
• Games (Go)
• Percolation
• Least common ancestor
• Equivalence of finite state automata
• etc..

Thanks, Coursera for the amazing course and thank you for reading it 😛.

PS. More information about UF algorithms can be found in the course-related book's chapter.

I have found an interesting post about interviewing recently.

Actually, I don’t really like this categorical approach. But there are my solutions have been written in Ruby.

Problem 1

Write three functions that compute the sum of the numbers in a given list using a for-loop, a while-loop, and recursion.

Solution

def sum_1(list)
  sum = 0
  for n in list do
    sum += n
  end
  sum
end

def sum_2(list)
  j, sum = 0, 0
  size = list.size
  while j < size do
    sum += list[j]
    j += 1
  end
  sum
end

def sum_3(list, sum = 0)
  return sum if list.empty?
  sum += list.pop
  sum_3(list, sum)
end

Problem 2

Write a function that combines two lists by alternatingly taking elements. For example: given the two lists [a, b, c] and [1, 2, 3], the function should return [a, 1, b, 2, c, 3].

Solution

def zip(l1, l2)
  (l1.zip l2).flatten!
end

Problem 3

Write a function that computes the list of the first 100 Fibonacci numbers. By definition, the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two. As an example, here are the first 10 Fibonnaci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, and 34.

Solution

def fib(n)
  (2..n).inject([0, 1]) { |a| a << (a[a.size - 2] + a[a.size - 1]); a }
end

Problem 4

Write a function that given a list of non negative integers, arranges them such that they form the largest possible number. For example, given [50, 2, 1, 9], the largest formed number is 95021.

Solution

def max(list)
  list.permutation.to_a.map(&:join).map(&:to_i).sort.last
end

Problem 5

Write a program that outputs all possibilities to put + or - or nothing between the numbers 1, 2, …, 9 (in this order) such that the result is always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.

Solution

def solutions(n, result)
  numbers = (1..n).to_a
  permutations = ["+", "-", ""].repeated_permutation(n-1).to_a

  sequence = permutations.inject([]) do |a, o|
    a << numbers.zip(o).flatten.compact!.join()
  end

  sequence.select { |v| eval(v) == result }
end

solutions(9, 100)

# or just one line solution:
["+", "-", ""].repeated_permutation(8).to_a.map{|c| (1..9).to_a.zip(c).flatten.compact!.join() }.select { |v| eval(v) == 100 }