A brief word about socket options and network tricks in erlang
erlang_guy
1. You will obtain {error,einval} response and a message "Bad value on output port 'tcp_inet'"

if you gen_tcp:send(Sock, Bitstring) a bitstring which contains number of bits other then
(length(Bitstring) in bits) mod 8 == 0

2. Tcp sockets are opened in active mode by default.

So if you want to use
gen_tcp:accept
gen_tcp:recv
without getting fails & return codes {error,einval} in your code, you have to set

{active , false}

option on your socket. See

http://erlang.org/pipermail/erlang-questions/2004-December/013734.html

3. There is a {packet, N} socket option.
See how it works on

http://mindeavor.com/blog/erlang-tcp-socket-packet-options

Generally, you'd use {packet, 0}.

You can get out from a list! Can't you?
erlang_guy
Once I faced with such a task. You have a list of elements. Each element represents
a relative pointer to another element. For example, +3 means, that you have to move to the
3 elements to the right from current, and -1 means, that you have to move 1 element to the left from current.

You start from the first element. You have to calculate the number of steps to get out
from a list or say 'never' if it's impossible to get out.

And, you have to solve it with O(N) limitations for time and space(yeah, both!) and in
Erlang(of course. You're reading an artiсle about Erlang, aren't you?)

There are several statements.

1. Only binaries provides Indexing/pattern matching at constant time. So, they're used here.

2. You have to bear in mind, that there are 3 border cases, when you're getting out,
when you're getting into a forever cycle and when you're running into 0.(you can't move
neither to the left nor to the right)

Here's the picture:

list_travel

3. To deal with cycles you have to use 2 pointers - fast & slow. When fast == slow,
there's a loop and you can't get out. But here's a caveat: you have to compare
NOT current pointers(slow and fast), but you have to keep tracking positions in array
and check if slow pointer points to the same position as the fast one does!


-module(list_travel2).
-export([do_all/0, test_signedlist/1]).
-define(SIZE, 64).  % works only on 64-bit architectures(for now)

%list len is [1..100000]
%each element =  [-1000 000..1000 000] %FIXME isn't checked yet
%time, space = O(N)
%returns {ok, Jumps} | never

%according to
%http://stackoverflow.com/questions/3665702/binary-search-in-erlang-in-lgn-time
%the only datastructure which provides O(1) access time is binary.

%The main idea is: 2 pointers SLOW & FAST

do_all() ->
    %[Length, List, ExpectedJumps]
    TestCases = [
        [5, [2,3,-1,1,3], 4],
        [4, [1,1,-1,1], never],
        [7, [6,1,5,2,4,3,1000], 2],
        [0, [], 0],
        [1, [1], 1],
        [3, [1,0,-1], never],
        [3, [1,1,0], never],
        [5, [1,1,1,1,0], never],
        [7, [6,4,2,4,-1,-3,-5], 7],
        [1, [-1], 1]
    ],
    io:format("~-20s~-10s~-15s~n", ["List", "Expected", "Real"]),
    io:format("~45c~n", [$-]),
    display_testcases(TestCases).

display_testcases([]) -> ok;
display_testcases([H|T]) ->
    [Length, L, Expected] = H,
    io:format("~-20s~-10s~-15s~n",
        [io_lib:write(L),
         io_lib:write(Expected),
         io_lib:write(travel(Length, L))]),
    display_testcases(T).

travel(Length, _) when Length =:= 0 -> 0;
travel(Length, _) when Length > 100000 -> badarg;
travel(Length, L) ->
    travel_helper(Length, sign_int_list_to_bin(L), 1, 1, 0, 0).

travel_helper(Length,Arr,CurrSlowPos,CurrFastPos,VisitedSlow,VisitedFast) ->
    %SlowOffset = Arr[CurrSlowPos]
    SkipSlow = ?SIZE*(CurrSlowPos -1),

    <<_:SkipSlow/bitstring,
    SlowOffset:?SIZE/signed-integer,
    _/bitstring>> = Arr,

    case SlowOffset of
        0 -> never;
        _ ->
            %FastOffset = Arr[CurrFastPos],
            SkipFast = ?SIZE*(CurrFastPos - 1),

            <<_:SkipFast/bitstring,
            FastOffset:?SIZE/signed-integer,
            _/bitstring>> = Arr,

            case FastOffset of
                0 -> never;
                _ ->
                    CurrFastPosNext = CurrFastPos + FastOffset,
                    if
                        CurrFastPosNext > Length; CurrFastPosNext < 1 ->
                            {ok, VisitedFast + 1};
                        CurrFastPosNext =:= 0 ->
                            never;
                        true ->
                            SkipFastFast = ?SIZE*(CurrFastPosNext-1),
                            <<_:SkipFastFast/bitstring,
                            CurrFastPosNextNextOffset:?SIZE/signed-integer,
                            _/bitstring>> = Arr,

                            CurrFastPosNextNext =
                                CurrFastPosNext + CurrFastPosNextNextOffset,

                            NewSlowPos = CurrSlowPos + SlowOffset,
                            if
                                NewSlowPos > Length; NewSlowPos < 1 ->
                                    {ok, VisitedSlow + 1};
                                CurrFastPosNextNext > Length;
                                CurrFastPosNextNext < 1 ->
                                    {ok, VisitedFast + 2};
                                CurrFastPosNextNext =:= 0 ->
                                    never;
                                NewSlowPos == CurrFastPosNextNext ->
                                    never;
                                true -> travel_helper(Length,
                                                      Arr,
                                                      NewSlowPos,
                                                      CurrFastPosNextNext,
                                                      VisitedSlow + 1,
                                                      VisitedFast + 2)
                            end
                    end
            end
    end.

sign_int_list_to_bin(List) -> sign_int_list_to_bin_h(List, <<>>).
sign_int_list_to_bin_h([], Bin) -> Bin;
sign_int_list_to_bin_h([H|T], Bin) ->
    sign_int_list_to_bin_h(T, <<Bin/bitstring, H:?SIZE/signed-integer>>).

sbinint_to_list(B) -> sbtl(B, []).
sbtl(<<H:?SIZE/signed-integer,T/bitstring>>, L) -> sbtl(T, [H|L]);
sbtl(<<>>, L) -> lists:reverse(L).

test_signedlist(L) ->
    io:format("~p~n",[sbinint_to_list(sign_int_list_to_bin(L))]).


And output:

4> list_travel2:do_all().
List                Expected  Real           
---------------------------------------------
[2,3,-1,1,3]        4         {ok,4}         
[1,1,-1,1]          never     never          
[6,1,5,2,4,3,1000]  2         {ok,2}         
[]                  0         0              
[1]                 1         {ok,1}         
[1,0,-1]            never     never          
[1,1,0]             never     never          
[1,1,1,1,0]         never     never          
[6,4,2,4,-1,-3,-5]  7         {ok,7}         
[-1]                1         {ok,1}         
ok



To be totally honest: I can't guarantee that this implementation uses O(N) space, because
I'm not sure if only 1 binary match context is created per "travel_helper" call.

I'll investigate this and get back with investigation & fixes as soon as possible

tac in Erlang.
erlang_guy
Once I had an interview into a big international & well known software company.
Everything was rather good than bad, but at the end of my interview I asked an interviewer: "I know that I haven't done perfect. What can I do to impress you? Give me a task". And he gave.

Write the tac utility from scratch.
I told him, that I could give him an algorithm, but would it be enough? He told that it wouldn't be enough. And that I had to a complete industrial-grade application. In Python or Bash. And that I have only 15 minutes for this. And the brute-force solution when you read all the file line-by-line, then reverse line list & print it - doesn't count, because it's inefficient(if file is big, for example).

I should suspect that something was wrong. I knew that it's possible to write less or more precise algorithm, but it's impossible to write a complete utility(in given 15 minutes).


I had to bare in mind, that I was interviewing for a dev-OPS position. And probably I should have explained him why the industrial-grade application couldn't be written in 15 minutes. And probably that was a solution.

But instead of this I started to code. I was doomed for fail :)

But I didn't give up. Of course I haven't passed the interview. But I solved this task after the interview. Eventually.

Here's (just to compare) the tac source code in C. 703 lines(if count comments).

My implementation in Erlang(yeah, I know, it's quite raw, but never-the-less) took 59 lines(with comments. Read them, they're useful though).

Algorithm. Read constant size chunks of file from end. Chunk by chunk. When current chunk have been read successfully - try to display all it's full lines in reverse order. And we have to attach the remainder from the previous read/display block to the end of the first string to be displayed of current read/display block. If we got an error during positioning/reading of some chunk - we just read from the beginning all that is left to be read & display it.

Here we are:

-module(tac).

-include_lib("kernel/include/file.hrl").

-define(BUFSIZE, 512).

-export([do/1]).

display_go(NewlyRead, OldBuf) ->
    [Rest|Lines] = binary:split(NewlyRead, <<"\n">>, [global]),
    case Lines of 
        [] -> %there was no \n, so append just read to the current line
            <<NewlyRead/bitstring, OldBuf/bitstring>>;
        _ ->
            [LastLine|OtherLines] = lists:reverse(Lines),
            %actually glue on demand <<LastLine, OldBuf>>
            lists:foreach(fun(L) -> io:format("~s~n", [L]) end,
                [<<LastLine/bitstring, OldBuf/bitstring>>|OtherLines]),
            Rest
    end.
    
display_stop(NewlyRead, OldBuf) ->
    %FirstLine, which becomes Last :)
    LastLine = display_go(NewlyRead, OldBuf),
    io:format("~s~n", [LastLine]).

display_lines(File, Buf, OffsetFromEnd, LeftToRead) ->
    case file:position(File, {eof, OffsetFromEnd}) of    
        {ok, _NewPosition} ->
            {ok, NewlyRead} = file:read(File, ?BUFSIZE),
            %I could glue <<NewlyRead,Buf>> and make much simplier display/2
            %but it's better to glue them when needed in display/3
            %Also, RestBuf is needed to be saved, because it's not a string,
            %because we cut everything after RestBuf if there was \n after
            %RestBuf. So RestBuf is just a part of the next string OR
            %it's the First string
            RestBuf = display_go(NewlyRead, Buf),
            display_lines(File,
                RestBuf,
                OffsetFromEnd - ?BUFSIZE,
                LeftToRead - ?BUFSIZE);
        {error, einval} ->
            % we have to read LeftToRead bytes from the beginning of the buffer
            if 
                LeftToRead > 0 -> 
                    file:position(File, bof),
                    {ok, NewlyRead} = file:read(File, LeftToRead),
                    display_stop(NewlyRead, Buf);
                LeftToRead =:= 0 -> %, just display whatever left
                    display_stop(<<>>, Buf)
            end
    end.


do(Filename) ->
    {ok, #file_info{size = Size}} = file:read_file_info(Filename),
    {ok, File} = file:open(Filename, [read, binary]),
    display_lines(File, <<>>, -?BUFSIZE, Size),
    ok = file:close(File).


Don't hesitate to ask questions in comments :)

erlang & debug. HOWTO.
erlang_guy
There are a lot of debug howtos for erlang. Sometimes they're not obvious. Even official.
Maybe that's why many programmers say: "There is no good debugger for erlang. It's ugly. It's unusable. It's awkward. I won't use it."

I would argue. So I wrote this article to prove, that you can debug in Erlang.

Here's my own. It's for dummies :) Just do as it's written here and it will work. I promise.

I tested this on
Erlang/OTP 17 [erts-6.0] [source] [64-bit] [smp:8:8] [async-threads:10] [hipe] [kernel-poll:false]

and OSX 10.9.3

Here we go.

1. First of all you need to compile a module to be debugged with the debug_info flag.
It's done either by running erlang shell like

6> 1s-MacBook-Pro:qualification_increase a1$ erl
Erlang/OTP 17 [erts-6.0] [source] [64-bit] [smp:8:8] [async-threads:10] [hipe] [kernel-poll:false]

Eshell V6.0  (abort with ^G)
1> c(tac, [debug_info]).
{ok,tac}


or directly by running erlc

a1$ erlc +debug_info tac.erl


2. Now you have to invoke the erlang shell.

a1$ erl


3. Now in the erlang shell, which you've just started, start the debugger:

1> debugger:start().
{ok,<0.34.0>}


If you installed graphical libraries properly, you would see the following window:

Screen Shot 2014-06-18 at 17.22.11

Okay. Seems legit.

4. From the menu select "Module" -> "Interpret":

Screen Shot 2014-06-18 at 17.25.21

You'll see all files that were compiled with "debug_info" option. They'll be highlighted. Files without "debug_info" will be shadowed:

Screen Shot 2014-06-18 at 17.27.03

So you select there your module(in my case it's tac.erl). After that this module
appears in modules available for debug:

Screen Shot 2014-06-18 at 17.35.19

5. Now not so obvious part comes(for people who got used to the Microsoft IDEs, which sometimes too great :) ).

You have to set the checkbox "On Break":

Screen Shot 2014-06-18 at 17.39.31

By doing this, you guarantee, that when a trace event(a breakpoint) comes, the debugger
will catch it.

6. Now, actually, you have to set up a breakpoint. To do this

6a) double click on module you've just interpreted OR select from the
menu "Module" -> "" -> "View"

Screen Shot 2014-06-18 at 17.44.08

You'll see this:

Screen Shot 2014-06-18 at 17.50.15
(actually, you'll see YOUR code :) )

6b) Select from menu "Break" -> "Line Break.."

Screen Shot 2014-06-18 at 17.54.10

And enter there a line number where you want place your breakpoint to:
(in my case it's 38) A debugger will substitute the line number where are you at the moment. If the "Ok" button is not active, like here:

Screen Shot 2014-06-18 at 17.57.36

don't panic! Just press "space" then backspace/delete or just enter the line number
manually. And the "Ok" button will become active:
Screen Shot 2014-06-18 at 17.59.05

It's a victory! You've just set up your first breakpoint in Erlang! Condratulations!
(of course if you see the following):
Screen Shot 2014-06-18 at 18.00.56

7. You're on your way. It's left just to debug this evil program. To do this, return
back to your erlang shell
and call any function which is being exported by your module and which calls the code where your breakpoint is located. In my case I call "do/1" function:

2> tac:do("cat.txt").


If you done everything as I'd described, a debugger automatically would attach to the process which you interpreted first and then started from the shell:

And you'll see the victorious thing:
Screen Shot 2014-06-18 at 18.09.08

Condratulations! Now you can debug as you used to.
Tags: ,

Balanced binary search tree from sorted array
erlang_guy
This is kind a interview-task.
The main idea is - to make a tree, we get a middle of an array as a node, then left subtree will be built from left array and right - from right. Recursively.
It's body-recursive solution.

-module(bbt_sarr).

-record(treenode, {data=null, left=null, right=null}).

-export([bal_bintree/1]).

bal_bintree(L = [_|_]) -> mk_tree(L);
bal_bintree([]) -> #treenode{}.

% 1 non-tail-recursive solution
mk_tree(L = [_|_]) ->
    %second list is longer if rem = 1, or they're equal if rem = 0
    {Left, [N|Right]} = lists:split(length(L) div 2, L),
    #treenode{data = N, left = mk_tree(Left), right = mk_tree(Right)};

mk_tree([]) -> null.



3> bbt_sarr:bal_bintree([1,2,3,4,5,6,7]).  
{treenode,4,
          {treenode,2,{treenode,1,null,null},{treenode,3,null,null}},
          {treenode,6,{treenode,5,null,null},{treenode,7,null,null}}}


We've got this tree:

Shapes

custom splitting a list is faster than lists:split?
erlang_guy
Once upon a time I was curious if it was possible to write a custom lists:split analog, which would be faster...

And I found this

So I implemented my own version. I think, it's clearer & prettier ^_^.

Here it is:

-module(enh_split).

-export([split_list/1, standard_split/1, test_splits/2,
         display_tests/1, test_splits_print/1]).

%splits list in O(3n/2) time
split_list(List) -> split_list(List, List, []).

% O(n/2) when navigating, O(n/2) when clue the SH head
%orig, left, right
split_list([SH|ST], [_,_|FT], UnreversedLeft) ->
    split_list(ST, FT, [SH|UnreversedLeft]); 
split_list(Right, [_], UnreversedLeft) ->
    {lists:reverse(UnreversedLeft), Right};
split_list(Right, [], UnreversedLeft) ->
    {lists:reverse(UnreversedLeft), Right}. %O(n/2)


standard_split(L) ->
    lists:split(length(L) div 2, L).


test_splits_print(N) ->
    L = lists:seq(1, N),
    {
        {standard, timer:tc(?MODULE, standard_split, [L])},
        {enhanced, timer:tc(?MODULE, split_list, [L])}
    }.

test_splits(N, SplitFunction) ->
    {Time, _} = timer:tc(?MODULE, SplitFunction, [lists:seq(1, N)]),
    Time.

benchmark_split(Repeats, ListLen, SplitFunction) ->
    lists:sum(
        [test_splits(ListLen, SplitFunction) || _ <- lists:seq(1, Repeats)]
    )/Repeats.

display_tests(Repeats) ->
    Length = [10, 100, 1000, 100000, 1000000],
    [io:format("~p,~p~n", [
    N,  
    benchmark_split(Repeats, N, standard_split)/benchmark_split(Repeats, N, split_list)
    ]) || N <- Length].


Both fifty & hundred series experiment showed, that the greater list length is,
the less difference between standard lists:split & custom algorithm which saves O(n/2) time.
For a 10-element list custom algorithm is faster more than 2 times, but for a million-element list this difference shrinks slightly.

10> enh_split:display_tests(50).
10,2.125
100,1.2452830188679245
1000,1.3378640776699027
100000,1.4013206742389535
1000000,1.0362642180038937
[ok,ok,ok,ok,ok]
11> enh_split:display_tests(100).
10,1.4313725490196079
100,1.2401315789473684
1000,1.54022450888681
100000,1.4217447265512917
1000000,1.0342491245998005
[ok,ok,ok,ok,ok]


And now, graphically

for fifty-series:

fifty

for hundred-series:

hundred

It seems to me, that lists:split doesn't simply cut head till n/2...
And it's implemented in more efficient way.
I have to dig into the code. Some time :)

Post for people, who're looking for programmers.
erlang_guy
Recently I had an interview. Kidding. I've been doing interviews a lot(in Ukraine). But I just started tasting them in EU/US.

Here's one of mine.

I = Interviewer
M = Me


I: "We give you a task. You have to finish it as soon as possible, but there is no time limit. Also, there are restrictions in big-O which you have to bare them in mind. Also, there is a restriction - finish this task in plain Erlang."

M: "Okay."

I finished this task as soon as possible, the program was working & tested, fully documented in comments.

Everything would be ok, you'd thought, right, ha?
NO!

I was waiting for results and thinking: "I'm so cool guy, really. I've done everything as they wanted".

And during that, skype beeped and recruiter told me: "Everything is OK, but they told, that your code is dirty". So, "the client isn't happy & blah-blah-blah".

M:(not at loud) "F*ck. Are you kidding me? There WAS NO SUCH A RESTRICTION AS CODE CLEANLINESS".

If there was such, I would spend some time to make it, heck, CLEAN. In that case, I would maximize these parameters together.
So, it turned for me, like I saved time for task completion(the condition which had been explicitly given to me) and maximized my(PROFIT :) ), but, there was some condition which wasn't even GIVEN to me, and it completely knocked me out.

The point is:

1. For guys who hire. If you're so smart, please, specify ALL of your restrictions when you're giving a task to a candidate. Sometimes technical guys accept your task literally.

If you do so, a candidate considers you as a future colleague and a mr. good guy.
If you don't, you'll be an asshole in candidate's(and probably in your future colleague's) eyes.

2. For candidates.

Don't be so stupid, like I was. Don't trust interviewer. Be paranoid. Do your best in all senses, and don't expect, that you'll be hired at a place where you're being interviewed.
Only statistics. The more you try, the greater you chance is.

Keep breaking the wall!
Tags: ,

Binary concatenation
erlang_guy
Sometimes you are tempted to concatenate two binaries, like

<<A/binary,B/binary>>

But everything comes for some price. For binary concatenation in erlang this price is > O(1)

So, weight your profits & losses first.



Test:

47> m_pr:do_profile_small().
{6,<<1,1>>}
48> m_pr:do_profile_big().  
{6470789,
 <<1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
   ...>>}


6 vs 6470789 uSecs.

Tail recursive flatten
erlang_guy
The goal is: make a nested list flatten using tail recursion. To achieve this goal, you have to shift your mind a bit: you can remake/change not only accumulator, but several params simultanеously. In any way: not only cut, but construct also!

fl_tr(L) when is_list(L)-> fl_tr(L, []).        %helper wrapper
fl_tr([], R) -> lists:reverse(R);               %final clause/terminal condition

fl_tr([[]|T], R) -> fl_tr(T, R);                %the first element is an empty list, just skip it
fl_tr([[H|T1]|T2], R) -> fl_tr([H|[T1|T2]], R); %the first element is a non-empty list(first clause rip off empty ones),
                                                %move its head to the outer list head(for further processing),
                                                %and move its tail to the head of general tail
fl_tr([H|T], R) -> fl_tr(T, [H|R]).             %the first element is just an element - add to result(gotcha!)


Here how it works:

1> fl_tr([[[1,2], 3, [[[4,5],6],8]], [], 9]).
[1,2,3,4,5,6,8,9]
2> 

?

Log in