Skip to main content

Posts

Showing posts from September, 2018

Brute-forcing a seemingly simple number puzzle

From StackOverflow Something was bothering me for almost two decades. It was a pen and paper game that I learned when I was around 13. The rules are simple: on an empty 10x10 grid (100 squares in total) you put a number 1 on an arbitrary square. Starting from that square you can move horizontally or vertically jumping over two squares or diagonally jumping over one square. There you can place number 2 . Your task is to reach number 100 , filling all squares. You can not visit already visited squares. Here is an example of a solved game with a reduced 5x5 grid, starting at top-left corner: 1 24 14 2 25 16 21 5 8 20 13 10 18 23 11 4 7 15 3 6 17 22 12 9 19 On the other hand, if the program makes bad choices, we might get stuck without reaching the perfect score of 25 (on a reduced 5x5 grid): 1 8 2 9 16 13 5 17 14 10 4 7 15 3 6 19 12 18 11 Notice how we got stuck at number 19, unable to move anywhere and f

Thread pool self-induced deadlocks

Summary (reading time: 10 minutes) Deadlocks are caused by many threads locking the same resources Deadlocks can also occur if thread pool is used inside a task running in that pool Modern libraries like RxJava/Reactor are also susceptible A deadlock is a situation where two or more threads are waiting for resources acquired by each other. For example thread A waits for lock1 locked by thread B, whereas thread B waits for lock2 , locked by thread A. In worst case scenario, the application freezes for an indefinite amount of time. Let me show you a concrete example. Imagine there is a Lumberjack class that holds references to two accessory locks: import com.google.common.collect.ImmutableList; import lombok.RequiredArgsConstructor; import java.util.concurrent.locks.Lock; @RequiredArgsConstructor class Lumberjack { private final String name; private final Lock accessoryOne; private final Lock accessoryTwo; void cut(Runnable work) { try {