Setuid, Setguid and the Sticky Bit

Before getting into setups, let’s quickly review the permission bits as they are displayed by the classic “ls -l” command:

  • The first bit is the file/folder flag: ‘-‘ for file and ‘d’ for folders
  • The rest 9 bits are grouped in 3-bits groups:
    • The 3 groups are:
      • Owner: the rights for the owner of the file / folder
      • Group: the right for the group that was assigned for the file / folder
      • Others: all the users in the system (you will default here if you do not fit into the previous 2 lists)
    • The 3-bit permission groups are:
      • Read: you have the permission to read the file or to list the content of a folder
      • Write: you have the permission to write the file or to create, rename, or delete files within the folder, and modify the folder’s attributes
      • Execute: you can execute the file or enter the folder, and see the files and directories inside

By default, if a user is allowed to execute a file (according to the permission rules described above) the file will be executed with the rights of that user. Sometimes this is not enough. Sometimes, you need some special / specific rights during that process execution just because that process is accessing a special resource you normally do not have the rights to access it (usually this is about executing processes with root access but you can actually execute processes with non-root rights too). The classic example is the “passwd” executable which needs to edit some system configuration files (owned by too) like /etc/passwd, /etc/shadow etc. Displaying the permission bits for “passwd” shows the following:

> -rwsr-xr-x. 1 root root 27832 Jun 10 2014 /usr/bin/passwd

The bit that is interesting for us is the ’s’ one that is shown instead of the expected ‘x’ one in the “Owner” group. This bit combined with the ‘x’ bit on the “others” group means the following: any user in the system is allowed to execute the “passwd” executable (this right is provided by the ‘x’ bit in the “others” group) but the process execution will be performed with the rights of the file owner (this right is provided by the ’s’ bit in the “Owner” group), which, in this case, means that the “passwd” executable will be executed with “root” access right even if the execution can be initiated by any user in the system.

The example above referred to executing an executable with the right of the executable (file) owner. A similar workflow can be defined around the group ownership: you can execute an executable using the rights of the group assigned to that executable / file. The process is similar: the “Execute” permission bit in the “Group” category needs to be set to ’s’.

How to set the ’s’ bit for “Owner” and “Group”? Using chmod:

  • “chmod u+s filename” – sets the “Owner” execution bit to ’s’
    • Octal form: add a ‘4’ in front of the classic permission values: “chmod 4777 filename”
  • “chmod g+s filename” – sets the “Group” execution bit to ’s’
    • Octal form: add a ‘2’ in front of the classic permission values: “chmod 2777 filename”

NOTE: If, after setting the ’s’ bit you see a capital ’S’ when listing the permission bits, this means that you do not have the “execution right” set too. Just add the execution rights too to transform the ‘S’ into an ’s’.

Sticky bit

The most common use of the sticky bit is on folders. When a folder’s sticky bit is set, the filesystem treats the files/folders from it in a special way so only the file/folder owner or root can rename or delete the file. Without the sticky bit set, any user with write and execute permissions for the folder can rename or delete contained files, regardless of the file’s owner. Typically, this is set on the /tmp directory to prevent ordinary users from deleting or moving other users’ files.

How to set the sticky bit:

  • “chmod +t foldername”: when the sticky bit is set, you will see a ’t’ instead of the ‘x’ permission bit for the “Others” group
    • Octal form: add a ‘1’ in front of the classic permission values: “chmod 1777 foldername”

NOTE: If, after setting the ’t’ bit you see a capital ’T’ when listing the permission bits, this means that you do not have the “execution right” for the “Others”category set too. Just add the execution rights too to transform the ’T’ into an ’t’.

Posted in Unix | Leave a comment

Sudo

Sudo allows you to manage / control the use-case when a user wants to execute commands as another user (usually as “root” but not limited to the super-user).

The generic sudo rule

UserList HostList = (RunAsUser) CommandList

Aliases

  • You can assign an alias (a name) to a list of users (User_Alias), hosts (Host_Alias) or commands (Cmnd_Alias)
  • The alias name must have all capital letters and may have numbers but must start with a letter
  • Example
    User_Alias USERS_LIST1 = user_name1, user_name2, user_name3

UserList

  • The list of users this rule apply to
  • You can put
    • user names
    • OS user group (you need to prefix them with %): e.g %user_group
    • User ID (you need to prefix them with #): e.g #user_ID
    • Group ID (you need to prefix them with %#): e.g %#group_ID

HostList

  • The list of hosts the rule applies to
  • You can put
    • hostname
    • IP Address
    • Host_Alias

CommandList

  • Commands must have the full path
  • Commands may have wildcards (e.g. /bin/* -> this will allow running all the commands from /bin folder)
  • Commands may also have parameters to restrict running the commands only on these parameters. Again, we can use wildcards on the parameters too (e.g. /bin/cat /var/log*)

RunAsUser

  • The command will be executed on behalf (with the permissions) of this user. If RunAsUser is missing, the root is assumed (the commands will be executed as root). Else, you need to use the “-u” option to run the sudo command as that user.
    Example:

    user_name1 Host1 = (user_name2) /bin/cat
    > sudo -u user_name2 cat file.txt

    Here we are running the “cat” command as user “user_name2″

  • You can put
    • a user name: (user_name)
    • a list of users: (user_name1, user_name2)
    • a user alias: (USER_ALIAS)
    • a group name: (:group_name)

ALL
You can use this as a value for UserList, HostList or CommandList to eliminate any restrictions.

user_name1 ALL = (user_name2) /bin/cat

Here user_name1 will be able to run /bin/cat as user_name2 on all machines.

If 2 or more rules conflict, the last matching one will win.

Use ! to eliminate from lists

 User_Alias LIST1 = %user_group1, !user_name1

This means that LIST1 refers to all the users from the “user_group1″ group except for user “user_name1″
Excluding using “!” is very useful for UserList, HostList or RunAsUser but not that useful for CommandList as if you eliminate a certain command from the list, the user may copy that executable binary to a different name and still execute that command…

Testing

  • Run “sudo -l” to find our what sudo allows to run for the current user.
  • Run “sudo -U user_name1 -l” to find our what sudo allows to run for the user_name1 user.
    • !!!NOTE!!! Only root and users that can run ALL commands on the current host can use the -U option.

Defaults and Options

  • Defaults can be used to control the default behavior of sudo.
    • “Defaults OptionList”
    • Types of defaults
      • Boolean
        • Defaults option_name1 -> enables option_name1 option
        • Defaults !option_name1 -> disables option_name1 option
      • Integer: options take a number as parameter (option name and parameter are separated by an “=“ sign)
      • String: similar to Integer but the parameter is a String now
  • Options can be set globally using Defaults but they can also be set
    • Per User
      • Defaults:UserList OptionList
    • Per Host
      • Defaults@HostList OptionList
    • Per Command
      • Defaults!CommandList OptionList
    • Per RunAsUser
      • Defaults>RunAsUserList OptionList

Allowing commands to execute other commands

There are commands that can execute other commands. Sometimes, this can be a security issue. For example, you can allow users to execute the “less” command with root privileges. However, while in “less” you can execute other commands (press “!” then execute the command) with root privileges.

In order to forbid commands to execute other commands, user NOEXEC:
Example:

> user_name1 ALL=NOEXEC:/usr/bin/less

This will not allow user_name1 to execute commands while using less

> user_name1 ALL=NOEXEC:ALL, EXEC:command_name1

This will prevent command execution from any command except from “command_name1” which really needs to execute other commands.

Managing environment variables

Environment variables are handled in several ways by sudo:

  • Whitelist environment variables: by default sudo removes all environment variables except $TERM, $PATH, $HOME, $MAIL, $SHELL, $LOGNAME, $USER, and $USERNAME. “env_keep” lets you tell sudo to keep other environment variables:
    • Defaults:%group_name1 env_keep += “ENV_VARIABLE1″
      • keep “ENV_VARIABLE1” environment variable for all the users part of the “group_name1” group.
    • “+=“ means add the environment variable to the current list. “=“ means overwrite the environment variable list with the newly provided one. “-=“ means deleting the environment variable from the current list.
  • Blacklisting environment variables
    • “env_reset” is the option that tells sudo to delete all the environment variable except for selected few
    • “env_delete” allows you to specify environment variables that should be removed.
  • Allow users to keep their environment variables
    • Use SETENV / NOSETENV tags on commands to instruct sudo to keep or not the user’s environment variables.
      • user_name1 host_name1 = (user_name2)SETENV:command_name1
        • Here, user_name1 is able to run command_name1 on the host_name1 host using user_name1’s environment variables.
        • You must run sudo with -E option to take into account the SETENV tag, otherwise sudo will keep on stripping all environment variables
          • > sudo -E -u user_name2 command_name1
    • Use setenv option to always keep environment variables for a certain user
      • > Defaults:user_name1 setenv
      • Use NOSETENV for certain commands to override this setenv
      • Again, you need to run sudo with -E flag
  • Run command using the environment of the target user
    • use the “-i” flag to simulate a login using the target user account (target user dotfiles like .login and .profile will be executed). This way you can run a certain command using the target account environment.
      • > sudo -i -u user_name1 command_name1
        • In this case the command_name1 will be executed using the user_name1 environment variables.
      • Used when we want to run an application with some configurations that are taken from environment variables (e.g. Java apps). In such case, you create a user with all these environment variables set and you run the application as that user.

When running sudo, there are 4 environment variables that are being set:

  • SUDO_COMMAND: the command you have run under sudo
  • SUDO_USER, SUDO_UID, SUDO_GID: the original user name, user ID and primary group ID.

Setting environment variables

  • secure_path allows you to set the path that will be first used by sudo when searching for a command. If the command is not used in secure_path, then $PATH is being used. This way you can make sure that users will not use bogus versions of applications (e.g. a hacked version of passwd) by providing them in $PATH variable.
    • > Defaults secure_path=“path1 path2 path3″
  • env_file used to provide a file with the environment variables to be set
    • > Defaults env_file=“full_path_to_env_variables_file”
    • Sudo adds these environment variables before stripping out the environment, so list any added variables in an env_keep sudoers rule as well.
    • This overrides the user’s own environment variables!

Sudo vs su

  • sudo is used to control commands execution as another user (use sudo to run a command as a different user, not to switch user identity). su is used to “switch the user”, meaning that you log in as another user (after running su, you actually receive the prompt and can run multiple commands as the new user)
  • in order to sudo, the user needs to enter his own password (even if the command ends up being executed as a different user) because the user only needs to prove his identity; the actual permissions (is the user allowed to execute the command as the requested user) are managed by the admin through the sudoers file. In the case of su, the user needs to enter the targeted user password, because you actually change the identity.

Turning sudo into suif shell_noargs option is enabled and sudo is run without arguments then you will receive the root prompt (so, just like running su).

  • Defaults:user_name1 shell_no_args
  • Running “sudo -s” does the same thing as enabling shell_noargs option
  • “sudo su -m” – run a shell but retain the user’s own environment
Posted in Unix | Leave a comment

Unicode vs Encoding

In this post I am going to try to explain as quickly and easy as possible the difference between Unicode and Encoding.

But first, here is the problem those 2 concepts are aiming to solve: how do we represent different symbols / characters in computer’s world?

In the beginning there was ASCII, which was able to represent any character using a number between 32 and 127. Characters with codes less than 32 were called “unprintable” / “control” characters (e.g. 10 is “line feed”, 8 is back-space, etc). Thus, all ASCII characters could be stored in the first 7 bits of a byte and everyone was so happy thinking that a big problem was forever solved.

The biggest problem with the ASCII standard was that it focused to address the English language requirements. Soon, A LOT of “standards” emerged that started to use the rest of 127 values of the byte to encode specific characters / symbols required by other languages or various applications needs. Problems appeared when someone from England (for example) was sending a byte of value 130 having a certain meaning (according to a certain standard) but was interpreted in China or France according to a different standard.

This mess was addressed by the 2 concepts that are the focus of this post. And we need both concepts in order to address the issues described above because, as we will soon see, the big problem was split into 2 parts that were solved through Unicode and Encoding.

Unicode

Unicode solves the “labeling” / “ID-ing” problem: it’s purpose is only to make sure that it assigns a unique ID (a number) to any symbol used in the world. Unicode does not care how this number will be actually encoded by computers (this is going to be another standard job). Unicode is just making sure that any symbol will receive a unique ID (again – a number) – this ID is called “code point”. There is NO LIMIT on the number of symbols Unicode can handle because there will always be a number available to be associated with a new symbol. Oh, and another smart decision was made to ease the transition from ASCII to Unicode: the first 127 Unicode values will be assigned to the old ASCII characters.

Encoding

So, Unicode assigned a number to a symbol. Now, it’s time to encode that number in a way that would allow computers to easily / efficiently use them. This is the job of encoding standards. And, as usual when it comes to solving optimal / efficiency problems, there is more than one answer depending on the application. This is why there are several encoding standards that have been defined to address different use-cases: UTF-8, UTF-16, UTF-7, UCS-4 etc.

The most popular is (arguably) UTF-8 as it provides a very smart / concise way of encoding the Unicode codes. Here are the rules:

  • As mentioned above, the first 127 Unicode symbols are exactly the original 127 ASCII characters. These will be encoded as in the old ASCII days: on one byte. This has a very important consequence: the documents that contain mostly old-ASCII characters will continue to have a very efficient encoding according to this standard. Also, another nice thing is that an old document containing only old-ASCII characters will be correctly interpreted by using this standard (thus, you have backward compatibility to old-ASCII). Thus, the first rule is: if we encounter a byte that has the first (most significant) bit “0″, this means that we have a Unicode symbol encoded in a single byte: 0xxxxxxx (the 7 bits represented as “x” will contain the Unicode ID).
  • If the Unicode ID does not fit in 7 bits, the first step is to use 2 bytes. The code for 2 bytes is the following: 110xxxxx 10xxxxxx. In other words, the first byte starts with 2 bits of “1″ (signifying that we will use 2 bytes for encoding the Unicode symbol) followed by a “0″ bit and then the bits actually used for encoding the Unicode. The second byte starts with the bits “10” which signifies that this is a continuation byte. In summary, we have 5 bits in the first byte + 6 bits in the second byte, thus 11 bits available to encode Unicode IDs on 2 bytes.
  • If 2 bytes are not enough, we can use 3 bytes: 1110xxxx 10xxxxxx 10xxxxxx. The first byte starts with 3 bits of “1″ (signifying that we will use 3 bytes for encoding the Unicode symbol) followed by a “0″ bit and then the bits actually used for encoding the Unicode. The second and third bytes start with the bits “10” which signifies that these are continuation bytes. In summary, we have 4 bits in the first byte + 6 bits in the second byte + 6 bits in the third byte, thus 16 bits available to encode Unicode IDs on 3 bytes.
  • The same rule can be applied to encode on 4, 5 and 6 bytes (the upper limit). The code for 6 bytes encoding is: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx. As before, the first byte tells us how many bytes are used for encoding this Unicode symbol (6 bits of “1″ thus we’ll use 6 bytes) and the rest 5 bytes are all continuation bytes (starting with “10”). In the 6 bytes representation you have 31 bits available to hold a Unicode code.
  • Thus, with UTF-8, you can encode up to 2*31 or 2.147.483.648 Unicode symbols – quite impressive, right?

    Another very very important property of UTF-8 is that it allows you to move forward or backwards. What does this mean? Let’s say that you perform a SEEK operation in a file encoded with UTF-8. The byte that you read will tell you it it is a continuation byte (it starts with a “10”) or not. If the former, then you can choose to move forward or backward in the file, byte by byte until you reach the first byte that is this a continuation byte. That will be the place from where you can safely start interpreting UTF-8 codes.

    As mentioned before, UTF-8 is just one of the encoding standards available. To make sure that the decoder is using the right algorithm, whenever you send a document (e.g. mail, web page) you need to send the encoding information:

         email: Content-Type: text/plain; charset=”UTF-8″
         web page: <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
    

    Obviously this works with the assumption that a commonly agreed default encoding scheme (usually ASCII) will be used by default until the information about the encoding information is encountered. After that, this encoding information will be used to interpret the rest of the document (email or web-page), thus the encoding information needs to be provided as early as possible in the document.

Posted in Software Engineering | Leave a comment

Bash special parameters

$*

Expands to the positional parameters starting from one (the parameter with index “zero” is the script name). When the expansion occurs within double quotes, it expands to a single word with the value of each parameter separated by the first character of the IFS special variable.

Here is are some examples

#!/bin/bash
# Saved as bash_params_1.sh

echo "Printing \"\$*\":"
for a in "$*"; do
    echo $a;
done

We execute the script like this:

> bash_params_1.sh 1 2 "3 4"

it will output the following:

Printing "$*":
1 2 3 4

This means that in the case of “$*” all the positional parameters were concatenated in a quoted string (in this case, IFS had the default value of “ “). Because there is a quoted string, the for loop processed a single element.

Let’s change the value of IFS to “+”. We print both the value of “$*” and the output of the loop.

#!/bin/bash
# Saved as bash_params_1.sh

IFS=“+"
echo "Printing \"\$*\”:" "$*"
for a in "$*"; do
    echo $a;
done

After running the script with the same arguments we get the following:

Printing "$*": 1+2+3 4
1 2 3 4

What happened? The value of “$*” is indeed “1+2+3 4” as the 3 positional parameters were concatenated in a single quoted word using the new IFS. But why the loop output is still “1 2 3 4” and not the (somehow expected) “1+2+3 4”? The answer is due to “echo $a;”. In this case, $a is unquoted – in this case $a (which is indeed “1+2+3 4”) will be split (according to IFS) and the result of the split will be passed as multiple parameters to the echo command which outputs its arguments separated by spaces.

How to fix it? We quote “$a” to no longer allow the splitting when the echo command is applied.

#!/bin/bash
# Saved as bash_params_1.sh

IFS=“+"
echo "Printing \"\$*\”:" "$*"
for a in "$*"; do
    echo “$a";
done

The output now is the following:

Printing "$*": 1+2+3 4
1+2+3 4

Excellent. Now that we’ve understood “$*”, let’s see how $* is managed. We have the second script:

#!/bin/bash
# Saved as bash_params_2.sh

echo "Printing \$*:"
for a in $*; do
    echo $a;
done

which is executed with the same arguments as the first script:

> bash_params_2.sh 1 2 "3 4"

The output is the following:

Printing $*:
1
2
3
4

The $* is still a string where the 3 positional parameters have been merged (using the IFS) but this time the result is an unquoted string. When this string is processed by the for loop, it will simply generate all the words using the IFS separator. In this case, because IFS is the default “ “, even the 3rd positional parameter will be split in 2. We can see this by changing the IFS value:

#!/bin/bash
# Saved as bash_params_2.sh

IFS=“+"
echo "Printing \$*:"
for a in $*; do
    echo $a;
done

After executing the script again, we will get the following:

Printing $*:
1
2
3 4

As you can see, the 3rd positional parameter was left untouched by the for loop as the IFS used by the loop to break the input string is now “+”.

$@

Expands to the positional parameters, starting from one (again, the parameter with index “zero” is the script name). When the expansion occurs within double quotes, each parameter expands to a separate word.

What does this mean? The main difference between $* and $@ is that while $* is a word where all positional parameters have been concatenated using IFS, the $@ is an array, where each positional parameter is an element in that array!!!

Let’s see that in action: here is the 3rd script that is shows how both $@ and “$@“ work:

#!/bin/bash
# Saved as bash_params_3.sh

echo -e "\nPrinting \"\$@\":"
for a in "$@"; do
    echo $a;
done

echo -e "\nPrinting \$@:"
for a in $@; do
    echo $a;
done

We run it with the same parameters:

> bash_params_3.sh 1 2 "3 4"

The generated output is:

Printing "$@":
1
2
3 4

Printing $@:
1
2
3
4

In the “$@“ case, each positional parameter from the $@ array will be treated as a quoted string – that’s why we see the “3 4” treated as a single step by the for loop.

In the $@ case, is positional parameter from the $@ array will be treated as an unquoted string – this, the 3rd parameter (“3 4”) will be one again split by the for loop due to the fact that IFS is the default “ “.

$#

Expands to the number of positional parameters in decimal. For example, we have the following script:

#!/bin/bash
# Saved as bash_params_4.sh

echo -e "\nPrinting \$#:" $#

We run it with the same parameters:

> bash_params_4.sh 1 2 "3 4"

The generated output is:

Printing $#: 3

which is as expected as we have provided 3 parameters to the script.

$?

This provides the exit status of the last executed command from the most recent command pipeline. Here is an example:

#!/bin/bash
# Saved as bash_params_5.sh

ls bash_params_5.sh
echo -e "\nPrinting \$? after a successful ls command :" $?

ls x_bash_params_5.sh
echo -e "\nPrinting \$? after an unsuccessful ls command :" $?

We execute the bash_params_5.sh script with no parameters and the generated output is:

Printing $? after a successful ls command : 0
ls: x_bash_params_5.sh: No such file or directory

Printing $? after an unsuccessful ls command : 1

The first time we print $? we get the value 0 (zero) because the first ls command was successful. The second time, however, we get the value 1 as the ls command failed (we can see that from the error message too).

$-

This expands to the current option flags as specified upon invocation. The bash flags can be set:

  • implicitly by the shell itself
  • by using the set command

Here is the script to demonstrate this:

#!/bin/bash
# Saved as bash_params_6.sh

echo -e "\nPrinting \$-:" $-

After running the script with no parameters, we get the following output:

Printing $-: hB

this means that 2 option flags are active so far (these are being enabled implicitly by the shell):

  • h: Causes bash to remember (hash) where commands it has found using PATH are located (default).
  • B: brace expansion is enabled, which means that you can run a command repeatedly on a list of comma-separated parameters within braces. Example:
    > echo \"{These,words,are,quoted}\"
    

    will output

    "These" "words" "are" "quoted"
    

As said before, we can use the set command to alter the set of option flags. Here is an updated version of the previous script where we are enabling the “verbose” option:

#!/bin/bash
# Saved as bash_params_6.sh

set -v    # setting / enabling the “verbose” option
echo -e "\nPrinting \$-:" $-

The output will be now:

echo -e "\nPrinting \$-:" $-
Printing $-: hvB

There are 2 things to notice here:

  • first the command to be executed (“echo -e “\nPrinting \$-:” $-“) is first printed before the actual execution. That’s the effect of enabling the “verbose” option.
  • second, we can see that the list of enabled options is now “hvB” which means that “v” option has been added to the list.

$$

Expands to the process ID of the shell. Here is an example to show this:

#!/bin/bash
# Saved as bash_params_7.sh

echo -e "\nPrinting \$\$:" $$

b=0
for a in {1..1000000}; do
  b=$((a + b));
done
echo "b =" $b

Here we print the value of $$ and then we do a very length computation to keep the shell process running while we check the PID (Process ID) value).

We run the script with no parameters but we run it in background:

> bash_params_7.sh &

The scripts prints the $$ value of 35162 and then starts the lengthy computation. In the meantime, we run the ps command to see the processes that run. We get the following output:

  PID TTY           TIME CMD
35162 ttys000    0:01.38 bash bash_params_7.sh

As you can see, the ID of the process that runs our script is indeed 35162, he same ID from the $$ variable.

$!

Expands to the process ID of the most recently executed background (asynchronous) command. We can use the example above (the one showing $$) to demonstrate $!.

Remember that, after running “bash_params_7.sh &” we have demonstrated that the ID of the process that executed this script was saved in $$. The script was executed in background, thus after it completes, we can run the following command:

echo $!

We will see that the output is, again 35162 which is, indeed, the ID of the last process that was executed in background.

$0

Expands to the name of the shell or shell script. Quite trivial to demonstrate this. Here is the simplest possible script to demonstrate this:

#!/bin/bash
# Saved as bash_params_8.sh

echo -e "\nPrinting \$0:” $0

Executing this script we will get the following output:

Printing $0: bash_params_8.sh

$_

The underscore variable is set at shell startup and contains the absolute file name of the shell or script being executed as passed in the argument list. Subsequently, it expands to the last argument to the previous command, after expansion.

To demonstrate the first part of the statement above, we use a script similar with the one from the previous section:

#!/bin/bash
# Saved as bash_params_9.sh

echo -e "\nPrinting \$_:” $_

Executing this script we will get the following output:

Printing $_: bash_params_9.sh

Thus, if no commands were executed yet, the $_ parameter will contain the script name. What happens if we execute a command before printing $_?

#!/bin/bash
# Saved as bash_params_9.sh

ps -e -o pcpu,cpu,nice,state,cputime,args -m
echo -e "\nPrinting \$_:” $_

In this case, the script will output the following:

Printing $_: -m

meaning the last argument that was passed to the ps command.

Posted in Unix | Tagged | Leave a comment

Coins in Scala

In this article I’m gonna present my Scala solution for 2 quite popular coin related problems (ask Google for curiosity about these problems and you will see tones of answers). The full code implementation with tests attached can be found here: (https://github.com/mdfecioru/algos/tree/master/coins_scala)

So, what are the problems? Two of them (for now):

  • Giving a set of coin types (e.g. 1, 5, 10, 25 cents) in how many ways you can give a certain amount of money (e.g. 37 cents)?
  • Giving a set of coin types what is the minimum number of coins you can use to give a certain amount of money?

Problem 1: Total number of coins combination to give an amount of money
So, let’s see what we are really asked here: we need to generate a simple count of combinations and not all the combinations. Thus, we could say that the problem is a little bit simplified for us. The solution in Scala is as follows:

def countChange(money: Int, coins: List[Int]): Int = {
  def countChangeInner(money: Int, coins: List[Int]): Int = {
    if (money == 0) 1
    else if (coins.isEmpty || money < 0) 0
    else countChangeInner(money - coins.head, coins) + countChangeInner(money, coins.tail)
  }

  if (money == 0) 0
  else countChangeInner(money, coins)
}

As you can see, the solution is really straight-forward. First, we create an inner function in order to easily handle the case where provided amount of money is zero (0). Then the inner function’s job is to recursively generate new solutions. How to do that? Well… giving a list of coin types and an amount of money, there are 2 ways we can generate new solutions:

  • keep the coins list but reduce the amount of money: either we use the first coin in the list of coins and we continue the solution for the remaining amount o money (money – coins.head) using the same coins list
  • keep the money but reduce the coins list: we search solutions for the same amount of money but using a reduce list of coins list by removing the first coin type (coins.tail)

Recursivity ends in two cases:

  • either we have found a solution: we have reduced the amount of money by using our coins until we’ve reached with EXACTLY 0. In this case, we return 1, to increment the number of valid solutions.
    • NOTE: To differentiate between this happy case and receiving 0 from the beginning, we needed to define the countChangeInner function…
  • either we have found that the current option will not lead to a valid solution: this is identified by either reducing the coin type space (coins.isEmpty) or by finding out that we’ve ended-up dealing with a negative amount of money as a result of using a certain coin type. In this case, we return 0 to not modify the number of valid solutions.

Problem 2: Minimum number of coins to return a sum of money
So, this is a totally different problem compared with the first one: we are now asked to identify from the entire set of possible coins combinations that we can use in order to return a sum of money the minimum amount of coins we can use to return that sum. A recursive solution to this problem is presented below:

def minChangeRec(money: Int, coins: List[Int]): Int = {
  val cache = collection.mutable.Map[Int, Int]()
  val infinity: Integer = money + 1

  def minChangeRecInner(money: Int): Int = {
    if (coins.contains(money)) cache(money) = 1
    else if (cache.getOrElse(money, infinity) == infinity) {
      cache(money) = infinity
      for (c <- coins.filter(_ <= money))
          cache(money) = Math.min(1 + minChangeRecInner(money - c), cache(money))
      }
      cache(money)
    }

    minChangeRecInner(money)
    if (cache(money) == infinity) 0 else cache(money)
}

Even if the minChangeRecInner function seems a bit complex, the “magic” happens in the for loop which does the following:

  • for each coin (c) that we can use for the current sum (coins.filter(_ <= money)) we reduce the problem further on the recursivity path by saying that for a certain selected coin, the solution is 1 (the selected coin) plus the minimum set of coins we need to express the rest of the money (1 + minChangeRecInner(money – c)).
  • as the for loop will execute the work describe above, it will also store the minimum value produce by each coin in a local cache (cache(money))

What’s with the cache? Can we write the function without it? The answer, is yes, we could not use the cache but it is not recommended as the solution space generated by the recursivity will very quickly grow(see here a really good / complete explanation http://interactivepython.org/runestone/static/pythonds/Recursion/DynamicProgramming.html). The cache is used to store away the minimum coins used for a certain sum of money so that next time we need this information somewhere in the recursivity tree we can simply re-use it instead of re-executing a costly recursivity.

There is also an iterative solution to this issue that is implementing the Dynamic Programming way of problem solving: start with solving the problem for initial steps or smaller problem spaces and then us this information to slowly build-up the solution for the case you are interested in.

Translating the above statement for our problem: let’s find out the minimum amount of coins we can use to pay 0, 1, 2, 3 … and so on an us this information to slowly compute the minimum amount of coins needed to the amount of money we are interested in. The code for this solution is listed below:

def minChangeDP(money: Int, coins: List[Int]): Int = { 
  val minCoins = collection.mutable.ArrayBuffer[Int]() 
  val infinity: Integer = money + 1 

  for (m <- 0 to money) { 
    var coinCount: Int = m 
    if (m == 0) minCoins += 0 else minCoins += infinity 

    for (c <- coins.filter(_ <= m)) 
      if (minCoins(m - c) + 1 <= coinCount) { 
        coinCount = minCoins(m - c) + 1 
        minCoins(m) = coinCount 
      } 
    } 

  if (minCoins(money) == infinity) 0 else minCoins(money) 
}

As you can see, the approach here is that we start buy building solutions for our problem for all the values in the 0 to money interval. For each amount of money in this interval, we are trying to use the minimum solutions we have identified for sum of money less than the current value in order to compute the minimum for the current amount of money. How we do that? We look at each coin available and see if we use it together with the minimum we have computed for the amount of money less the selected coin value to get a better minimum number of coins for the current sum of money.

That’s what the “if (minCoins(m – c) + 1 <= coinCount)” line is doing: selecting the coin ‘c’ the rest of the money we need to may is ‘m-c’ and the minimum amount of coins to pay this amount is already computed: minCoins(m – c). Thus, if we select coin ‘c’ the minimum amount of coins will be 'minCoins(m – c) + 1’ to pay the amount of money ‘m’. We do this for all possible coins and compute the minimum between all these values – that’s going to be the actual minimum for the amount of money ‘m’. We save this and we go to the next step until we reach the ‘money’ value.

Cannot say “THE END” until I mention 2 articles that really helped me understand solving this problem:

Posted in Scala | Leave a comment

3, 2, 1 or Yet Another Productivity Tool

This is not a new idea at all… Ironically, you will find this in so many articles and books but many of us still seam to have difficulties in applying these concepts in practice. Leo Babauta was one of the authors that have tried to take great productivity ideas like the ones described David Allen’s “Getting Things Done” and worked on simplifying these heavy / complex frameworks and defining more practical and easy-to-adopt strategies. But can this be further simplified?

Recently I have completed this “Learning how to learn” course on Coursera which I do recommend for the really interesting and practical techniques presented (some of them being summarized in my previous article). One interesting idea was to stop focusing on the product, on the end-goal and instead focus on the process, on building the right / sustainable routine. The reason behind this technique is that, most of the time, the end-goal is so far away or so complex that it may seem discouraging… This is the perfect opportunity for procrastination to kick in and to ruin all your plans.

You plan to lose 10 kg in the next 2 months? It’s sooooo hard… You plan to learn for that difficult exam or to get that monstrous certification? It’s soooo much work in front of me… If you look at the problem this way, it’s discouraging. And if you felt this way you need toy understand that it’s perfectly normal – most of us would feel the same…

Another way of looking at this challenges is to setup a routine that would take you to that goal with a pace you feel comfortable with. You will find out that replacing the above mentioned goals with “I’m gonna do 30min exercise every day and eat healthy” or “I will spend 2 hours each day studying” routines will transform the so-hard-to-achieve goals into something more easier to accept and with similar results.

So, now we know the theory… How do we turn this into practice? First, here is more theory. Here are some things you need to accept as absolute truth:

  • you cannot focus on something that really requires your attention / creativity more than 2 hours and still be productive
  • your brain cannot multi-task
  • not all your work is equally important and urgent

Now we are ready to define a simple strategy to put all this in practice – I call it “3, 2, 1” or, in more words, “3 tasks of 2 hours per 1 day”.

  • Step 1: make sure you properly label in 2 buckets: ToDo (work that is important for you and MUST be done at some point) and SomedayMaybe (things that are not that important but you want to process it whenever you have some spare time – e.g. read articles, see presentations, etc)
  • Step 2: for each day define (reserve) up to 3 slots of work of up to 2 hours each. It would be great if you could do this at the end of a day to plan for the next day (do not recommend to plan for more than 1 day ahead giving how much assumptions change from one day to another). Depending on your day (how fragmented / busy it is) you will find room in your calendar for 3 slots or less – that’s fine. Just make sure that:
    • you have at least one slot of work defined (otherwise you will simply not advance with your work)
    • one work slots should not be bigger than 2 hours (otherwise your productivity will simply drop)
    • do not plan for more that 3 work slots per day (even if your think can schedule more work)
  • Step 3: Each day, make sure you use the reserved work slots to work on the topics you planned for. The goal is not necessarily to finish something during that slot but merely to advance toward finishing a work that needs to be done. Remember: we are focusing on the process, not the goal. We are implementing a working routine instead of trying to define slices of work that may be finished in a work slot.
  • Step 4: when you finish going through the planned work slots and you find out that you have more available time in that day, you have several alternatives:
    • you may plan for another work slot for that day – NOT recommended
    • you may take topics from the SomedayMaybe list (this is a great opportunity to consume this list) – recommended
    • you may relax or rest or reward yourself for staying true to this routine – HIGHLY recommended

This process allows you to achieve several things:

  • first accept that you do not have the entire day available for doing work that matters to you but allows you to best take advantage of your whatever available time by splitting it into 2 hours chunks where you can keep your productivity levels high
  • then turns your shift from focusing on the end-goals to implementing a routine where you make sure that every day you have time reserved for advancing toward the end-goal. More over, this routine is a sustainable one: no more than 3 slots of up to 2 hours each per 1 day. Spending more effort on focused-work while claiming to be productive is doubtful
  • gives you the opportunity to be flexible depending on how each day looks like (how many meetings / interrupts you may have) and also gives you the opportunity to have time for rest, relaxation or consume the SomedayMaybe list if you feel like

ENJOY!

Posted in Personal Development | Leave a comment

Learning how to learn

I’ve just finished this “Learning how to learn” (https://www.coursera.org/learn/learning-how-to-learn/home/welcome) course on Coursera which is full of interesting, easy to use and practical ideas for improving your memory and ability to learn new things. Definitely a course that I highly recommend.

Here are some concepts I connected instantly with, not because they were necessarily new for me but mostly because I have first discovered them myself and used them a lot without knowing that these were, in fact, well known learning techniques.

Use metaphors and analogy to help simplify matters
Using metaphors or analogy to simplify a hard / complex topic is a really powerful way of learning, of remembering easily that complex topic later on.

My favorite example here is bloom filters. These are basic algorithms that allow someone to get an answer to a question like “Giving a set of numbers, is the number X part of this set?” and you get the answer to this question very very fast. The problem with this algorithm is that if the answer is NO than it’s 100% accurate while if the answer is YES the accuracy is not 100%.

How can you remember this with a simple metaphor? Have you ever seen those cartoons where Bugs Bunny is being chased by Daffy Duck who is being chased by Yosemite Sam who is being chased by a dog and so on? And at some point they where all going through a mountain of snow, each of them leaving their shape in that snow-wall. A bloom filter is exactly that: once Bugs Bunny went through that snow-wall once, if it will try to go again, the hole that was already done in the snow-wall will fit it (Bugs already went through it once). If a huge elephant will try to go through the snow-wall hole, it will not be able to do it, thus we can conclude that the elephant was not in the original set that created the show-wall hole. HOWEVER, is a small mouse will try to go through, it will be able, because it’s smaller than all the ones that have modeled the snow-wall hole. That’s why the YES answer is not 100% reliable. Got it?

Another example is the excellent picture that explains the difference between precision and recall: a couple of topics I’ve had some difficulties to remember until this picture came in: https://en.wikipedia.org/wiki/Precision_and_recall

Difference between focused and diffuse thinking
There are two modes of thinking we should be aware of:
– focused: keeps your thoughts concentrated on solving problems you are somewhat familiar with like, for example, solving an arithmetical problem or finding a rime for a word. You access this mode simply by clearing all distractions around you and focusing on the problem you need to solve.
– diffuse: allow for more broad ranging way of thinking that will help you understand a new / hard topic you want to learn. You access this mode simply by doing those natural things that let you brain slowly drift away from the focus mode: get a walk or drift off to sleep.

Knowing when to use the diffuse mode and not rely solely (and for an extended amount of time) on the focused mode is really important for learning new / hard things. Start by focusing directly on the topic you want to learn and then look for ways to get into diffuse mode – you will find that once your brain will start drifting away from the focused mode it will start automatically work in the background to make connections between the new things we are trying to learn and the concepts we’ve already mastered: these are the new neural structures that allow us to learn something new.

Example: I remember in high school that I was required to learn a new poem or parts of novels every week. A technique I’ve learned during those days was to force myself to learn the poem in the evening just before going to sleep. The goal was to be able to recite it by heart at least once, even if I was doing a lot of mistakes (now I know that this was going to focused mode). Then, I went to sleep. Everytime (really) next morning I found out that I was able to recite the poem much much better, with less mistakes (this was the diffuse mode in action).

Tackling procrastination
Focus on the process rather than the product (or the end goal). The reason is simple: if you focus on the end-goal and that goal is so far away or seems so impossible to reach, then, naturally, procrastination will kick in and you will be so tempted to give up. Examples like loosing weight or learning for that big exam may be so familiar to you.

However, if you focus on implementing a process that will get you to the desired goal, you will instantly see results. What does it mean?
Instead of aiming to lose 10 kg in the next 2 months (focus on product), aim to go to the gym 30 min every day and eat healthier (focus on process). Focus on this and weight yourself in 2 months – you’ll be pleasantly surprised (even if you’ll find out that you’ve only lost 7 kg).
Instead of aiming to learn for that incredibly difficult and horrifying exam (focus on product), aim to study 2 hours each day (focus on process). You will be really surprised how much of the exam material will be processed in only 2 weeks, for example.

Also make sure that you “eat your frogs first” – start with tacking the most difficult topics first. Completing them will give you the energy to overcome whatever comes next.

Oh… I almost forgot! A very important technique that will help avoiding procrastination is making sure you reward yourself upon completing those small time-boxes of learning efforts. But, and this is important, make sure hat you delay your reward until after the time-box for learning has expired!!!

My favorite saying that perfectly describes this technique is: “How do you eat an elephant? One bite at a time.”

Learning and “spaced-out” repetition
The goal of this technique is to get things out from the working memory (a limited space that can hold very little information for a small amount of time) into the long term memory (this is where the information is being safely stored for a long time).
To achieve this, learning new stuff, understanding it and the moving to the next interesting thing will often not do. Instead, any new topic we’ve just learned needs to be repeated for several times before moving on. But repeating it for a few times within the same hour is not efficient either. A much more efficient technique is when the repetition interval is gradually “spaced-out”: first repetition happens after 1 day, the next one after another 2 days, third one after a week.
Testing yourself whenever you have a chance to check that the new information was indeed safely stored into the long-term memory is an efficient learning technique too.

AND MOST IMPORTANTLY: Sleep and exercise
Sleep helps washing away toxins that develop during our day’s activities. Thus make sure you always get enough sleep and, more important, do not plan to sacrifice the night before an important exam by replacing the sleep with “working” – this will rarely give you any results.
Exercise (cardio for example) is so important for improving both our memory and ability to learn as exercise helps increasing the numbers of new neurons that are being born and survive in the hippocampus (an important part of your brain for memory and learning functions).

Besides the advantages mentioned above, both sleep and exercise are also opportunities for you to use to kick the diffuse way of thinking whenever you feel you need it.

Posted in Personal Development | Leave a comment