ssledz blog

Everything should be made as simple as possible, but no simpler.

Write to an HFS+ USB Drive From a Synology NAS

It is realy annoying that the newest version of Synolgy DSM (5.2-5644 Update 1) can’t handle properly hfs+ hard drive device out of the box. Thanks to the fact that many users had the same problems as me before I found realy quickly handy article which shows how to make easy workaround. The trick is to disable journaling on the drive and then try to remount the device in nas with ro flag switched off.

So to be able to write to an HSF+ USB drvie you need first

  • disable journaling on the drive
  • connect your drive to nas
  • remount device with ro flag switched off

Disabling journaling in the drive

To be able to do this you need to plug in your device to the mac (I couldn’t do this from my linux). Then to turn journaling off using Disk Utility do following:

  • open Disk Utility (located in Applications/Utilities).
  • select the disk device to disable journaling on.
  • choose Disable Journaling from the File menu.

For someone this option could not be visible (Mac OS X 10.4 and later) then before clicking on the File menu press and hold Option key

More you can find here

Remount device with ro flag switched off

First log in as a root to the ds. Then have a look how the drive is mounted

1
2
3

ds> mount
/dev/sdq1 on /volumeUSB1/usbshare1-1 type vfat (utf8,umask=000,shortname=mixed,uid=1024,gid=100,quiet)
/dev/sdq2 on /volumeUSB1/usbshare1-2 type hfsplus (ro,force,uid=1024,gid=100,umask=000)

You can spot that the drive is mounted with the ro(read only) flag.

Now unmount the drive.

1

ds> umount -f /dev/sdq2

And remount so it is writable using the same info used when it was mounted automatically.

1

ds> mount -t hfsplus /dev/sdq2 /volumeUSB1/usbshare1-2

Finally, you can notice that device is no longer mounted as read only.

1
2
3

ds> mount
/dev/sdq1 on /volumeUSB1/usbshare1-1 type vfat (utf8,umask=000,shortname=mixed,uid=1024,gid=100,quiet)
/dev/sdq2 on /volumeUSB1/usbshare1-2 type hfsplus (0)

To prove this try.

1
2
3
4

ds> ls /volumeUSB1/usbshare1-2/ | grep 'sampleDir'
ds> mkdir /volumeUSB1/usbshare1-2/sampleDir
ds> ls /volumeUSB1/usbshare1-2/ | grep 'sampleDir'
sampleDir

Note

It is very important to switch off journaling in the drive. When you remount the drive with ro switched off and haven’t yet disabled the journaling in the drive you won’t be able to write anything to the disk though mount will print that the drive is mounted as writable.

Git-svn Kata - First Release

I have just released first version of git-svn kata. It is good starting point for those who prefer to use git but are stuck with svn. At the moment there are only two kata, but soon will be much more. To start just clone my repo

1

git clone git@github.com:ssledz/gitsvnkata.git

and run first one

1
2

cd kata-1-checkout-svn-project-std-layout
./start-kata.sh

All solutions are available here

Standford's Automata Online Course - Course Review

Automata course was six weeks long. Before taking the course I had some prior knowledge about automata, regular expressions, context free grammar, turing machine and np-completeness. In my opinion most of the lectures was clear and understandable. I found it very helpful to have a quizzes during each one. They were keeping me up on the track for a whole time. After each module there was a homework consisting of some test questions. For me those homeworks were the most valuable components of the course. It helped me a lot to fully understand the materials.

Of course not everything was straight forward. The most dificult topic, for me, was np-completeness. To be honest I didn’t fully understand it. I can only guessing that it was caused by the fact that I haven’t spent as much time during study as I should. Maybe I will return to that but now there are much more important things to do on top of my todo list.

After taking a final exam I have earned Statement of Accomplishment attached below.

Java Development Environment With Vagrant - Part 1

Preface

This post describes my development environment driven by Vagrant (Full description what can be found there is here). You can ask why Vagrant ? To be honest this is my first adventure with this tool. I am suprised how easy can be the process of setting brand new development environment. This tool can really save plenty of hours.

What is Vagrant (based on documentation)

Vagrant provides easy to configure, reproducible, and portable work environments built on top of industry-standard technology and controlled by a single consistent workflow to help maximize the productivity and flexibility of you and your team. Sounds cool, isn’t it? One can configure the whole development environment with all the tools, needed libraries and various dependencies and other can just based on that create his own brand new development environment. The Process of introducing new team members into the project can be shortened by the time of setting new development environment.

Vagrant Providers

Vagrant has an ability to manage some of machine types like

  • VirtualBox
  • VMware
  • Docker
  • Hyper-V

In my setting I am using Virtualbox which is a free cross-platform consumer virtualization product supported by Oracle. To use this provider VirtualBox must be installed on its own. VirtualBox can be installed by downloading a package or installer for your operating system and using standard procedures to install that package.

Vagrant Installation

Visit the downloads page and get the appropriate installer or package for your platform. Then install it using standard procedures for your operating system. The installer will automatically add vagrant to your system path so that it is available in terminals.

Setting development environment

To set up java development environment You need just type the following bunch of commands

1
2
3

git clone git@github.com:ssledz/vagrant-boxes.git
cd vagrant-boxes/java-dev-environment
vagrant up

Now vagrant box image is downloading from the box repository and then installation script provision.sh will be called.

The provision.sh trace can look following

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

==> default: Creating directories
==> default:     Creating bin directory
==> default:     Creating public_html directory
==> default:     Creating servers directory
==> default: Installing packages
==> default:     apt-get update
==> default:     Installing vim
==> default:     Installing git
==> default: Installing mc
==> default:     Installing libssl-dev libreadline-dev zlib1g-dev
==> default:     Installing make g++
==> default:     Installing apg
==> default:     Installing mysql-server
==> default:         Creating /etc/mysql/conf.d/utf8_charset.cnf
==> default:         Restarting mysql
==> default:     Installing nginx-core ssl-cert
==> default:         Creating /etc/nginx/sites-available/public_html
==> default:         Enabling /etc/nginx/sites-available/public_html
==> default:         Restarting nginx
==> default: Downloading jdks
==> default:     jdk-5u22-linux-x64.tar.gz is available
==> default:     jdk-6u45-linux-x64.tar.gz is available
==> default:     jdk-7u80-linux-x64.tar.gz is available
==> default:     jdk-8u65-linux-x64.tar.gz is available
==> default: Installing jdks
==> default:     Extracting jdk-5u22-linux-x64.tar.gz
==> default:     Extracting jdk-6u45-linux-x64.tar.gz
==> default: Extracting jdk-7u80-linux-x64.tar.gz
==> default:     Extracting jdk-8u65-linux-x64.tar.gz
==> default:     Cleaning
==> default: Installing apache-maven
==> default:     Downloading apache-maven-3.3.3-bin.tar.gz
==> default:     Extracting apache-maven-3.3.3-bin.tar.gz using tar
==> default:     Cleaning
==> default:     Creating symbolic link apache-maven
==> default: Installing apache-ant
==> default:     Downloading apache-ant-1.9.6-bin.tar.gz
==> default:     Extracting apache-ant-1.9.6-bin.tar.gz using tar
==> default:     Cleaning
==> default:     Creating symbolic link apache-ant
==> default: Installing gradle
==> default:     Downloading gradle-2.8-bin.zip
==> default:     Extracting gradle-2.8-bin.zip using unzip
==> default:     Cleaning
==> default:     Creating symbolic link gradle
==> default: Installing sbt
==> default:     Downloading sbt-0.13.9.tgz
==> default:     Extracting sbt-0.13.9.tgz using tar
==> default:     Cleaning
==> default:     Creating symbolic link sbt
==> default: Installing environment managers (for Java, Ruby, node.js and Python) 
==> default:     Installing jenv
==> default:         Clonning from github to ~/.jenv
==> default:         Setting environment variables
==> default:         Make build tools jenv aware
==> default:             ant plugin activated
==> default:             maven plugin activated
==> default:             gradle plugin activated
==> default:             sbt plugin activated
==> default:     Installing rbenv
==> default:         Clonning from github to ~/.rbenv
==> default:         Installing plugins that provide rbenv install
==> default:     Installing nodenv
==> default:         Clonning from github to ~/.nodenv
==> default:         Installing plugins that provide nodenv install
==> default:     Installing pyenv
==> default:         Clonning from github to ~/.pyenv
==> default: Updating .bashrc
==> default: Install runtimes using environment managers
==> default:     Install java
==> default:     Set jdk 1.8 globally
==> default:     Install ruby
==> default:     Install node.js
==> default:     install python
==> default: Installing apache-tomcat
==> default:     Downloading apache-tomcat-8.0.28.tar.gz
==> default:     Extracting apache-tomcat-8.0.28.tar.gz using tar
==> default:     Cleaning
==> default:     Creating symbolic link apache-tomcat
==> default:     Creating apache-tomcat /bin/setenv.sh
==> default:     Copying tomcat-users.xml to apache-tomcat/conf
==> default:     Creating /etc/init.d/tomcat script
==> default:     Starting tomcat

To loggin to the machine do

1

vagrant ssh

To check what can You find in this environment please visit this page.

More about how to use this setting to develop in the next post.

Virtual Box VDI Compaction

Virtual Disk Image (VDI) files grow over time. If You discover that VDI on the host system is much bigger than used space on the guest partition it is time for compaction.

  1. Install zerofree tool (apt-get install zerofree).
  2. Remove unused files (apt-get autoremove, apt-get autoclean, orphaner --guess-all).
  3. Reboot the guest system in single user mode (Grub menu will appear if you press and hold Shift during starting, then hit e when Grub boot appear and append single option to the Grub boot parameters).
  4. Remount filesystems as readonly (mount -n -o remount,ro -t auto /dev/sda1 /).
  5. Fill unused block with zeros (zerofree /dev/sda1). It’s time consuming operation. If You have other disk devices (e.g. /dev/sda5) then also perform zerofree on each one.
  6. Shutdown the system (poweroff).
  7. Compact VDI files on the host system (VBoxManage modifyhd my.vdi compact). It’s time consuming operation.

Instead points 1,3-5 to fill free space with zeros You can do following (You don’t need to boot in single user mode)

  1. sudo dd if=/dev/zero of=/bigemptyfile bs=4096k
  2. sudo rm -rf /bigemptyfile

Octopress Pushing Error to GitHub

When You get something like that

1
2
3
4
5
6
7
8

## Pushing generated _deploy website
To git@github.com:ssledz/ssledz.github.io.git
 ! [rejected]        master -> master (non-fast-forward)
error: failed to push some refs to 'git@github.com:ssledz/ssledz.github.io.git'
hint: Updates were rejected because the tip of your current branch is behind
hint: its remote counterpart. Integrate the remote changes (e.g.
hint: 'git pull ...') before pushing again.
hint: See the 'Note about fast-forwards' in 'git push --help' for details.

just do following

1
2
3

cd _deploy
git reset --hard origin/master
cd ..

and try again

1
2

rake generate
rake deploy

Context Free Grammar Will Help Where Regex Pattern Fail - Is This Well Formed Array ?

Preface

Some times ago I was scanning Stackoverflow to find a puzzle to solve, and I found one guy was trying to write a piece of software which had needed to answer on one simple question. Is given expression a well formed array? He was searching for a ready to use regular expression but he failed, because this puzzle can’t be solved using regex engine. Why, I will explain later but now I can say that this puzzle can be easily solved using Context free grammar.

Well formed array

You can ask what does the well formed array mean ? I will try to answer by providing some positive and negative examples of such arrays.

1
2
3
4
5
6

[1 2 [-34 7] 34]
[1 2 [-34] [7] 34]
[1 2 [-34 [7] 34]]
[1 2[-34[7]34]]
[]
[[[]]]

Above are well formed arrays. In opposite below are expressions which are not syntactically consistent with the definition of well formed array.

1
2
3

[1 2 -34 7] 34]
[1 2 [-34 [7] 34]
[][]

Studying those examples we can try to answer on this question. So well formed array is an expression which fulfills following requirements

  • first, no blank, character is an open brace '['
  • the last no blank character needs to be a closed brace
  • inside array, integers and other well formed arrays can appear
  • integers are separated with at least one blank character

Why not regex ?

Let’s simplified our example. Let’s say that we want to write a regular expression which will generate following words 

1
2
3
4

[]
[[]]
[[]]
[[[]]]

You can notice that the mention above strings are a subset of the set of strings which we want to parse. And here I don’t have also good news. We can’t use regex engine to parse such strings. Why is it not possible ? Simply speaking regex engine modeled by a Finite Automata (FA) can’t count how many '[' we have already used and check that the same number of ']' must appear just after the last '['. FA doesn’t have stack to remember such things. If You are curious about formal proof you can try to google Pumping Lemma phrase. Pumping Lemma provides You a useful tool to proof if a given language (set of words which fulfill given conditions) is not a regular.

Context free grammar

I have already mentioned that to solve our problem (if a given array is well formed) we need to write a parser of some context free grammar. The model of Context free grammar is a Finite Automata with a stack. Thanks to this an Automat is able to remember some facts that have happened (e.g count braces). To write a parser we need first to write down a grammar for expression of well formed array. To do this I will use ebnf (Extended Backus–Naur Form) form.

1
2
3
4

array = "[", { array-body }, "]" 
array-body = number | array
number = [ "-" ], digit, { digit }
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;

Now we are ready to write a parser. To be precise I will use top-down parsing strategy which let me directly transform written above grammar into set of recursively called procedures.

Parser

It is a good manner to split parser into 2 parts

  • lexer
  • parser

Lexer is responsible for grouping letters into tokens. In our grammar we have 4 kinds of tokens

  • '[' (LB)
  • ']' (RB)
  • number (NUMBER)
  • end - token informing that there is no letter left on input (END)

Tokens are expressed by a class Token written below

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public class Token {

    public enum Type {
        LB, RB, NUMBER, END
    }

    private final Type type;
    private final String value;

    public Token(Type type, String value) {
        this.type = type;
        this.value = value;
    }

    public Type getType() {
        return type;
    }

    public String getValue() {
        return value;
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("Token[");
        sb.append("type=").append(type);
        sb.append(", value='").append(value).append('\'');
        sb.append(']');
        return sb.toString();
    }
}

Lexer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

public class Lexer {

    private int current;
    private String input;

    public Lexer(String input) {
        this.input = input;
    }

    private char getChar() {
        return input.charAt(current++);
    }

    private void unputChar() {
        current--;
    }

    private boolean hasNextChar() {
        return current < input.length();
    }

    public Token next() {

        if (!hasNextChar()) {
            return new Token(Type.END, "");
        }

        char c = getChar();

        while (Character.isWhitespace(c)) {
            c = getChar();
        }

        if (c == '[') {
            return new Token(Type.LB, "[");
        }

        if (c == ']') {
            return new Token(Type.RB, "]");
        }

        int s = 1;
        if (c == '-') {
            s = -1;
        } else {
            unputChar();
        }

        StringBuilder buffer = new StringBuilder();
        while (hasNextChar()) {

            c = getChar();

            if (Character.isDigit(c)) {
                buffer.append(c);
            } else {
                unputChar();
                break;
            }

        }

        return new Token(Type.NUMBER, s > 0 ? buffer.toString() : "-" + buffer.toString());

    }
}

Parser

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

public class Parser {

    private Lexer lexer;
    private Token currentToken;

    private boolean match(Type type) {
        return type == currentToken.getType();
    }

    private void consume(Type type) {
        if (!match(type)) {
            throw new RuntimeException(String.format("Should be %s is %s", type.name(), currentToken.getType().name()));
        }
        currentToken = lexer.next();
    }

    private void array() {

        consume(Type.LB);

        while (true) {

            if (match(Type.NUMBER)) {
                consume(Type.NUMBER);
            } else if (match(Type.LB)) {
                array();
            } else {
                break;
            }

        }

        consume(Type.RB);
    }


    private void parse(String line) {

        lexer = new Lexer(line);
        currentToken = lexer.next();

        array();
        consume(Type.END);

    }

    public boolean isWellFormedArray(String line) {

        try {
            parse(line);
            return true;
        } catch (Exception e) {
            System.out.println(String.format("%s is not a proper array because %s", line, e.getMessage()));
            return false;
        }

    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public class ParserTest {

    @Test
    public void testIsWellFormedArray() throws Exception {

        Parser parser = new Parser();
        assertThat(parser.isWellFormedArray("[1 2 [-34 7] 34]"), equalTo(true));
        assertThat(parser.isWellFormedArray("[1 2 -34 7] 34]"), equalTo(false));
        assertThat(parser.isWellFormedArray("[1 2 [-34] [7] 34]"), equalTo(true));
        assertThat(parser.isWellFormedArray("[1 2 [-34 [7] 34]"), equalTo(false));
        assertThat(parser.isWellFormedArray("[1 2 [-34 [7] 34]]"), equalTo(true));
        assertThat(parser.isWellFormedArray("[]"), equalTo(true));
        assertThat(parser.isWellFormedArray("[][]"), equalTo(false));
        assertThat(parser.isWellFormedArray("[[]]"), equalTo(true));
        assertThat(parser.isWellFormedArray("[1 2[-34[7]34]]"), equalTo(true));

    }
}

Puzzle - Write a Method to Generate the Nth Fibonacci Number

Preface

Writing a method to generate the nth Fibonacci number is not a rocket science. The recursive formula for that is very simple and can be written following:

1
2
3

fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

The n-th Fibonacci number is just the sum of two previous Fibonacci numbers and the first and second formula are our ‘base cases’. Based on this we can write a method public static long slowFibonacci(int n)

1
2
3
4
5
6
7
8
9

public static long slowFibonacci(int n) {

    if (n == 0 || n == 1) {
        return n;
    }

    return slowFibonacci(n - 1) + slowFibonacci(n - 2);

}

You have already noticed that instead of writing fibonacci I have written slowFibonacci. There is a reason for that and You may guessing that probably we can do something with this method to make it much faster and You have right. There is a quite usful programming method which we can use to improve the performance of this method. However before doing this let’s try to write a method call stack trace for let’s say 5th Fibonacci number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

slowFibonacci(5)
-slowFibonacci(4)
--slowFibonacci(3)
---slowFibonacci(2)
----slowFibonacci(1) -> 1
----slowFibonacci(0) -> 0
---slowFibonacci(2) -> 1
---slowFibonacci(1) -> 1
--slowFibonacci(3) -> 2
--slowFibonacci(2)
---slowFibonacci(1) -> 1
---slowFibonacci(0) -> 0
--slowFibonacci(2) -> 1
-slowFibonacci(4) -> 3
-slowFibonacci(3)
--slowFibonacci(2)
---slowFibonacci(1) -> 1
---slowFibonacci(0) -> 1
--slowFibonacci(2) -> 1
--slowFibonacci(1) -> 1
-slowFibonacci(3) -> 2
slowFibonacci(5) -> 5

The number of dashes means how many delayed operations is on the stack. Dash followed by the ‘>’ (‘->’) means that the operation can be computed (return value is provided) and removed from the stack.

You can notice that the same operations are evaluated many times, for example slowFibonacci(2) is computed 3 times. It is obvious waste of cpu resources. What can we do to use previously computed value instead of evaluating it again and again ?

Dynamic programming

‘Dynamic programming’ method comes to our rescue. According to the wiki, ‘dynamic programming’ is a method for solving a complex problem by breaking it down into a collection of simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems and optimal substructure. The dynamic programming approach seeks to solve each subproblem only once, thus reducing the number of computations: once the solution to a given subproblem has been computed, it is stored or “memoized”: the next time the same solution is needed, it is simply looked up.

What does it mean for us ? Each already solved subproblem (computed i-th Fibonacci number) can be saved in the let’s say global array and if the same solution is needed just simply look for it in that table.

Coding

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public class Fibonacci {

    private static long[] FIB = new long[100];

    public static long fibonacci(int n) {

        if (n == 0 || n == 1) {
            return n;
        }

        if (FIB[n] != 0) {
            return FIB[n];
        }

        FIB[n] = fibonacci(n - 1) + fibonacci(n - 2);

        return FIB[n];

    }

    public static long slowFibonacci(int n) {

        if (n == 0 || n == 1) {
            return n;
        }

        return slowFibonacci(n - 1) + slowFibonacci(n - 2);

    }

}

Call stack trace for this tuned method is following

1
2
3
4
5
6
7
8
9
10
11
12
13

fibonacci(5)
-fibonacci(4)
--fibonacci(3)
---fibonacci(2)
----fibonacci(1) -> 1
----fibonacci(0) -> 0
---fibonacci(2) -> 1
---fibonacci(1) -> 1
--fibonacci(3) -> 2
--fibonacci(2) -> 2
-fibonacci(4) -> 3
-fibonacci(3) -> 2
fibonacci(5) -> 5

You can notice that the number of calls is much smaller then for slowFibonacci(5).

At the end I would like to present a simple benchmark

1
2
3
4
5
6

fibonacci(45) = 1134903170
Duration: 0,002000s
fibonacci(60) = 1548008755920
Duration: 0,000000s
slowFibonacci(45) = 1134903170
Duration: 7,893000s

To compute 45-th Fibonacci number for fibonacci it takes 2ms and for slowFibonacci it takes 7.8s so a savings are significant.

Puzzle - Write a Method That Return All Subsets of a Set

Problem

Write a method public static Set<Set<String>> subsets(Set<String> set) which returns all subsets of a given set. From mathematics point of view we need to compute the power set of the given set. The number of such subsets can be easily computed because it just 2 to the power of ‘number of element in a set’. So for a set consisting of 3 elements it is 8. To proceed let’s write some examples.

1
2
3
4
5
6
7
8
9

subsets({'a'}) = {} + {'a'}
subsets({'b'}) = {} + {'b'}
subsets({'c'}) = {} + {'c'}

subsets({'b','c'}) = {} + {'b'} + {'c'} + {'b','c'}
subsets({'a','c'}) = {} + {'a'} + {'c'} + {'a','c'}
subsets({'a','b'}) = {} + {'a'} + {'b'} + {'a','b'}

subsets({'a', 'b', 'c'}) = {} + {'a'} + {'a','b'} + {'a','c'} + {'a','b','c'} + {'b'} + {'b','c'} + {'c'}

Based on that we can notice a following pattern

1
2
3
4
5
6
7

subset('a')            = {}, {'a'}
subset('b')            = {}, {'b'}
subset('c')            = {}, {'c'}
subsets({'b','c'})     = subset({'b'}) + subset({'c'}) + {'b','c'}
subsets({'a','c'})     = subset({'a'}) + subset({'c'}) + {'a','c'}
subsets({'a','b'})     = subset({'a'}) + subset({'b'}) + {'a','b'}
subsets({'a','b','c'}) = subsets({'b','c'}) + subsets({'a','c'}) + subsets({'a','b'}) + {'a','b','c'}

Coding

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public static Set<Set<String>> subsets(Set<String> set) {

    if (set.size() == 1) {
        Set<Set<String>> ret = new HashSet<>();
        ret.add(new HashSet<>());
        ret.add(new HashSet<>(set));
        return ret;
    }

    Set<Set<String>> ret = new HashSet<>();
    ret.add(set);

    for (String e : set) {

        Set<String> newSet = new HashSet<>(set);
        newSet.remove(e);
        Set<Set<String>> subsets = subsets(newSet);
        ret.addAll(subsets);

    }
    return ret;

}

1
2
3
4
5
6
7
8
9

public static void main(String[] args) {
    Set<String> set  = new HashSet<>(Arrays.asList("a", "b", "c", "d"));

    Set<Set<String>> subs = subsets(set);
    System.out.println("size: " + subs.size());
    for(Set<String> sub : subs) {
        System.out.println(sub.toString());
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

size: 16
[]
[a]
[b]
[c]
[a, b]
[d]
[a, c]
[b, c]
[a, d]
[b, d]
[a, b, c]
[c, d]
[a, b, d]
[a, c, d]
[b, c, d]
[a, b, c, d]

Puzzle - Write a Method to Reverse a String Using Recursion

Problem

I bet that everyone who is reading this know how to write a method to revers the string, but does everyone know how to do it using recursion ? To face such puzzle it it always a good idea to write first some results for given arguments and try to find a pattern. There always must be a ‘base case’ which can’t be divided into subproblems. We also need to discover a procedure which solves bigger problem using its smaller subproblems.

So let’s say we need to write a method public static String revers(String arg) which for a given argument returns a reversed string. Below I have written some examples.

1
2
3
4
5

revers('a')     = 'a'
revers('ab')    = 'ba'
revers('abc')   = 'cba'
revers('abcd')  = 'dcba'
revers('abcde') = 'edcba'

Based on that we can already write a recursive procedure.

1
2
3
4
5

revers('a')     = 'a'
revers('ab')    = 'b'|revers('a')
revers('abc')   = 'c'|revers('ab') 
revers('abcd')  = 'd'|revers('abc')
revers('abcde') = 'e'|revers('abcd')

To compute a reversed string for 'a' we need to return that string and it is our ‘base case’. In other cases to compute a reversed string we need to get the last char and concatenate it with the reversed string without that last character.

I think we are ready to write some code.

Coding

1
2
3
4
5
6
7
8

public static String revers(String arg) {

    if (arg.length() == 1) {
        return arg;
    }
    return arg.charAt(arg.length() - 1) + revers(arg.substring(0, arg.length() - 1));

}

1
2
3
4
5
6
7

public static void main(String[] args) {
    System.out.println(revers("a"));
    System.out.println(revers("ab"));
    System.out.println(revers("abc"));
    System.out.println(revers("abcd"));
    System.out.println(revers("abcde"));
}

1
2
3
4
5

a
ba
cba
dcba
edcba