head k* && g++ -fsanitize=address -static-libasan -g -O -Wall -std=c++14 k.cpp k2.cpp && ASAN_OPTIONS=detect_odr_violation=1 ./a.out

How to see git/mercurial branch on your command line

Add this to your `~/.bashrc` file:


function parse_git_branch () {
git branch 2> /dev/null | sed -e '/^[^*]/d' -e 's/* \(.*\)/ (\1)/'
}

function hg_dirty() {
hg status --no-color 2> /dev/null \
| awk '$1 == "?" { unknown = 1 }
$1 != "?" { changed = 1 }
END {
if (changed) printf "!"
else if (unknown) printf "?"
}'
}

function hg_branch() {
hg branch 2> /dev/null | awk '{ printf " (" $1 ")" }'
hg bookmarks -a 2> /dev/null | awk '/\*/ { printf " (" $2 ")"}'
}

RED="\[\033[0;31m\]"
YELLOW="\[\033[0;33m\]"
GREEN="\[\033[0;32m\]"
NO_COLOR="\[\033[0m\]"

DEFAULT="[37;40m"
PINK="[35;40m"
RANGE="[33;40m"

PS1="$GREEN\u@\h$NO_COLOR:\w$YELLOW\$(parse_git_branch)$YELLOW\$(hg_branch)$NO_COLOR\$ "

Google Code Jam 2016. Problem D – Fractals.

Google Code Jam 2016 – solution to problem D: Fractiles.

This is problem to get 10 points for free.
Small part is very easy.

Problem text.

Problem 4 - Fractals.
If S = K this means that we can use K positions to test if there is gold.
We will use all of them.

Let’s assume there is gold in 1st position of original sequence.
Then 1st position of final sequence will be gold too – this is very easy to understand.

So we choose 1.

If there is no gold at 1st position – it means that first K numbers in final sequence are the same as in original.
So small solution which wirks for all inputs:

1 2 3 4 … K

To solve large input next idea becomes a solution:

Let’s imagine some start sequence and end sequence which has complexity C=2.
How we can clean 1 tile and check if 2 origina tiles contain gold or not?

Here is image which explains which tile we need to check to verify tiles 1 and 2 in original sequence.

Tiles - Complexity = 2

This easily becomes feasible idea for solution – for complexity C – each additional level allows us to check +1 original tile by cleaning corresponding tile in corresponding position.

Minimum number of tiles which are required is floor(K / C)

 

How to configure Presto/Hive/HDFS on Mac

It is quite a pain to setup everything.
Here are some links which helped me significantly:

Tricks:

Use java 1.7 with newest hadoop/hdfs/hive 2.0.0

To create metastore – go to $HIVE_HOME/bin and run:

schematool -initSchema -dbType derby

Derby is java in-memory database. This option will not allow you to run simultaneously Hive metastore (required for Presto) and Hive itself and so consider using mysql for metastore.

Then install presto going through instructions on prestodb.io

So to use presto – you need to shutdown Hive CLI and start metastore service from same directory where your derby is being set with schematool. To start metastore:

hive --service metastore

To check which components of Hive/HDFS are running on machine, run:

jps

To start datanode:

hdfs datanode

Create 2 aliases in ~/.bashrc to start/stop hadoop/hdfs:

alias hstart="/usr/local/Cellar/hadoop/2.7.1/sbin/start-dfs.sh;/usr/local/Cellar/hadoop/2.7.1/sbin/start-yarn.sh"
alias hstop="/usr/local/Cellar/hadoop/2.7.1/sbin/stop-yarn.sh;/usr/local/Cellar/hadoop/2.7.1/sbin/stop-dfs.sh"

Left Semi Join on Hive

Instead of writing:

SELECT a.key, a.value
FROM a
WHERE a.key in
 (SELECT b.key
  FROM B);

Let’s write:

SELECT a.key, a.val
FROM a LEFT SEMI JOIN b ON (a.key = b.key)

So LEFT SEMI JOIN is just allows to implement efficiently IN/EXISTS queries’ semantics in your queries.

Note that right hand side of query cannot be used in WHERE clauses – it should only be used in ON join condition.

Slate – windows manager for Mac

I have discovered Slate – windows manager for Mac which is doing exceptionally great job in improving my productivity.

Begin with reading of this article from Tristan Hume on how to start working with Slate:

http://thume.ca/howto/2012/11/19/using-slate/

And here is slate by itself with full tutorial:

https://github.com/jigish/slate

Here is part of config which explains the idea:


config windowHintsShowIcons true
config windowHintsIgnoreHiddenWindows false
config windowHintsSpread true
config windowHintsDuration 5

bind esc:cmd hint

alias mon-laptop      1680x1050
alias mon-monitor     2560x1600

alias right-top move screenOriginX+screenSizeX/2;screenOriginY                   screenSizeX/2;screenSizeY/2 ${mon-monitor}
alias right-bottom move screenOriginX+screenSizeX/2;screenOriginY+screenSizeY/2     screenSizeX/2;screenSizeY/2 ${mon-monitor}
alias left-top move screenOriginX;screenOriginY                                 screenSizeX/2;screenSizeY/2 ${mon-monitor}
alias left-bottom move screenOriginX;screenOriginY+screenSizeY/2                   screenSizeX/2;screenSizeY/2 ${mon-monitor}
alias full-screen move screenOriginX;screenOriginY                                 screenSizeX;screenSizeY ${mon-laptop}

bind pad9:cmd ${right-top}
bind pad3:cmd ${right-bottom}
bind pad7:cmd ${left-top}
bind pad1:cmd ${left-bottom}
bind pad5:cmd ${full-screen}

Here is my full config:
https://gist.github.com/mgalushka/d79c68464f191ba8e11a

I use next combinations to manage windows:

cmd+number on pad panel – I use it to move current active window to corresponding position: to corners/half the screen up and down.

For window hints I use cmd+esc

Find process_id to be killed

Very often I need to kill some background job in unix.

To do this, I need to find its process_id to be passed to


kill -9 process_id

to be killed properly.

Here is quick way to combine finding process id for specific job:


ps aux | grep [my-fancy-filter-to-find-a task] |\
         awk '{print $2}'

This will just print process_id for my task to be killed.

Caution! Please, use this with care as if your grep return not the process_id  you are expecting – you may get to a trouble.