failing like never before


Why I Hate Remote Working

(Because titles with broad, sweeping statements (that may not actually totally reflect the author's opinion) are wonderful at garnering attention... So maybe read all the way through before deciding to lambaste me?)

I work in the Silicon Valley and my team works with people scattered across America, Singapore, Israel, and India. A terrific feat, that without technologies like desktop sharing, VoIP, and IM would be virtually impossible. Many tech companies support and even encourage remote workers these days. And why shouldn't they? It allows the company to hire the best engineers around the world without having to worry about providing a physical space for the engineers to work out of.

But communicating with people that are 12 hours ahead of you is hard. At 9 PM in California, it's 9:30 AM in India. So by the time that 9 PM meeting is done, it's 10 PM (or 1 AM(!) on the east coast), just enough time to talk "off-line" to individual people, wrap up loose ends, and go to sleep. You'll try to share the pain, alternating who has to take the late night meeting, so that everyone only loses one night a week. But things don't always work out according to plan. People are busy or sick, so meetings get moved, and then the management bureaucracy rears it's head and suddenly you're spending two or three nights a week in meetings.

Do you need some help from your co-workers that are abroad? Well I hope you enjoy working till 2 AM to accommodate their schedule. Do make sure to load up on coffee before tomorrow's 9 AM meeting.

And you'll especially love dragging yourself to work for your early morning meeting only to find it's been rescheduled (Hey, it was your fault. Maybe you should have checked your e-mails before you drove to work).

Social life? What's that? Maybe you'll make the mistake of going out with friends and accidentally miss your 8 PM meeting, much to the displeasure of your manager(s).

So now that I've raised your ire and piqued your interest, I can afford to be a little more reasonable. I do in fact work quite a lot, but it is not a 24/7 lifeless schedule. I have no trouble working with people in the midwest or the east coast; the time difference is not so substantial to be a burden. I've on occasion worked from home, or some other remote location and found it to be fairly easy and enjoyable.

This is not my attempt to publicly flame my company or deride my co-workers or managers. I actually like my company and enjoy the people I work with, but like all relationships it often needs work. The idea of remote workers working closely together as a team is relatively new to this world and difficult to pull off. They are plenty of success stories (just look at the open source community), but also many stories more like mine. I do not believe we created this globally distributed team without fully considering it's implication or the strain it would place on the engineers, and now that we're knee deep into it, happiness and normalcy is a long slog away.

TLDR: Long distance relationships are hard work. Make sure you've considered the challenges and set guidelines before you jump feet first into it.


Knight’s Tour in Lisp

For those of you unfamilar with the Knight's tour, here's a brief overview of the problem. The Knight's Tour invovles placing a knight on a chessboard and then having the knight move to each and every square on the chessboard once and only once. There are a suprisingly huge number of possible paths that a single Knight can take on a standard chessboard so of course, a blind, exhaustive search is generally out of the question. 

The program I have written below explores the Open Knight's Tour, where the knight simply has to reach each and every square once and only once (the Closed Tour would add the additional requirement that the knight end on the square he started on). I will admit that my Lisp code isn't exactly the best or the most efficient, but it works fairly deccent. My method of solving the tour, uses backtracking (which is very similar to Depth First Search) and a herustic known as Minimum Remaining Value. This herustic is sometimes known as Warnsdorff's algorithm when used in the Knight's Tour. Warnsdorff's algorithm selects as the knight's next move, the square that would present the fewest possible moves following the move to that square. Essentially, the herustic is trying to eliminate dead end's earlier on. And so here's my code (most of which is comments, [Hey, it was written for a class]):

;;; FIND-KNIGHTS-TOUR2                                                      ;;; 
;;; using minimum remaining value herustics (aka most constrained variable) ;;;
;;;                                                                         ;;; 
;;; on my laptop, this implementation can find a solution to                ;;;
;;; 100x100 board, starting from (1 1) in under three minutes               ;;;
;;; and can solve 50x50 in about 16 seconds on SEAS                         ;;;
; you can run the knights tour with:
; (find-knights-tour ([rows in board] [cols in board] [row_pos] [col_pos])

(setq steps 0)
(setq visited-list ()) 

; generate a list of all possible moves for knight
; given that current position of knight is (row col)
; note that this function will generate "wrong" move values, like
; moving off the board or moving to an old spot.
; function get_values(number:x number:y):((num num) (num num) )
(defun get_values (row col)
    ; there are at most eight possible move values 
    (list (+ row 2) (+ col 1))
    (list (+ row 2) (- col 1))
    (list (+ row 1) (+ col 2))
    (list (+ row 1) (- col 2))

    (list (- row 2) (+ col 1))
    (list (- row 2) (- col 1))
    (list (- row 1) (+ col 2))
    (list (- row 1) (- col 2))) )

; val is a list of possible move values for a knight variable
;   and should be generated by get_values function
; m_row is max number of rows in the board
; m_col is max number of columns in the board
; test_valid_values will return a list containing only the valid
; values allowed, removing those values that have already been
; visited and are not on the board
; function test_valid_values( 
;       ((num num) (num num) ):vals
;       number:m_row
;       number:m_col):((num num) (num num) )
(defun test_valid_values (vals m_row m_col)
    ; grab the first value out of the vals list
    ((v (car vals)))
    ((null vals) ()) 
    ; test for out of bound values, or already traversed
    ; if value is out of bound, remove it (cdr vals) 
    ((or (> (car v)  m_row) (<= (car v)  0) 
         (> (cadr v) m_col) (<= (cadr v) 0)
         (list_member v visited-list))
            (test_valid_values (cdr vals) m_row m_col))
    ; value is valid, add to our "valid" list
    (t (cons (car vals) 
             (test_valid_values (cdr vals) m_row m_col))))) )

; check if "l" is a member of "visited"
; return 't' if so, 'nil' otherwise
; function list_member( 
;       (number number):l
;       ((num num) (num num) ):visited) :t/nil
(defun list_member (l visited)
    ((null visited) nil)
    ((equal (car visited) l) t)
    (t (list_member l (cdr visited)))) )

;minimum remaining value herustic, or the most constrained variable
;instead of just returning randomnly arranged list of possible moves from
;   current location (as in above without herustics) arrange possible moves
;   in the list so that the move that will offer the least number of moves in
;   the next iteration comes first, with the move that offers the most of 
;   moves coming last in the list
;function min_remaining_val(number:m_row number:m_col): 
;       ((number number) (number number) )
(defun min_remaining_val (m_row m_col)
    ; get valid values
    ((vals (test_valid_values 
        (car (car (last visited-list))) (cadr (car (last visited-list)))) 
             m_row m_col)))
    ; then call call mrv_helper to attach assign a value to each move
    ; mrv_sort to arrange moves 
    (mrv_sort (mrv_helper vals m_row m_col))

; determines number of possible moves allowed if we move to a position in
; the vals list
; function mrv_helper(
;   ((num num) (num num) ):vals
;   number:m_row
;   number:m_col) :
;   ((num (num num)) (num (num num)) )
(defun mrv_helper (vals m_row m_col)
       ; calculate the number of possible moves from a position in the 
       ; "vals" list
           (get_values (car (car vals)) (cadr (car vals))) 
         m_row m_col))))
      ; if no more moves in "vals", just return it and done
      ((null (cdr vals)) (list (cons len (list (car vals)))))
      ; else add move and length value to list and keep recursing
      (t (cons (cons len (list (car vals))) 
                 (mrv_helper (cdr vals) m_row m_col))))) )

;finds the move with the minimum value in the list "vals"
;i.e. if "vals" is ( (1 (2 4)) (2 (5 2)) (4 (3 2)) )
;   then min_vals would return (1 (2 4)) because its move value is "1"
;function min_val(
;   ((num (num num)) (num (num num)) ):vals) :
;       (num (num num))
(defun min_val (vals)
    ; base case, return the only move in "vals"
    ((null (cdr vals)) (car vals))
        ; calculate the min_val in the rest of the list
        ; store it in "p"
        ((p (min_val (cdr vals))))
          ; if the current minimum value is less then previous
          ; min val, then use current min val
          ((<= (car (car vals)) (car p)) (car vals))
          ; else use previous min val
          (t p))))) )

; remove from list 'l' the element that matches 'r'
; this is because we are not allowed to use "remove" function
;function remove_list(list:r list:l):list
(defun remove_list (r l)
    ; if equal, then done
    ((equal r (car l)) (cdr l))
    ; reached the end and couldn't find a match
    ((null (cdr l)) l)
    ; else keep recursing
    (t (cons (car l) (remove_list r (cdr l))))) ) 

; sort the moves in "vals" list based on their move length values
; and then strips out their "length values
; i.e., if "vals" is ((3 (2 3)) (2 (1 2)) (5 (3 4)) (1 (2 1)) (2 (2 2)))
;then mrv_sort returns:
;   ((2 1) (1 2) (2 2) (2 3) (3 4) )

;function mrv_sort(
;   ((num (num num)) (num (num num))  ):vals) :
;   ((num num) (num num) )
(defun mrv_sort (vals)
    ; base case, return the last move in "vals"
    ((null (cdr vals)) (cdr (car vals)))
        ;else keep sorting, using min_val function 
        ;v is the min val in "vals"
        ((v (min_val vals)))
        (append (cdr v) (mrv_sort (remove_list v vals)))))) )

; recurse down the search tree, expand out the children for last
; visited spot
; m_row is number of rows in board
; m_col is number of cols in board
; function recurse_down(number:m_row number:m_col):t/nil
(defun recurse_down (m_row m_col)
  ; get the valid values, store as val
    ((vals (min_remaining_val m_row m_col)))
      ; no valid values, backtrack 
      ; note, that we test for sucessful completion before this 
      ((null vals) nil)
      ; else recurse across
      (t (recurse_across vals m_row m_col)))) ) 

; this function is exactly the same as recurse_across except
; that it calls recurse_down instead of recurse_down
;vals is valid moves, having the form:
;     ((number number) (num num) etc.)
; m_row is number of rows in board
; m_col is number of cols in board
; function recurse_across(
;       ((num num) (num num) ):vals
;       number:m_row
;       number:m_col) : t/nil
(defun recurse_across (vals m_row m_col)
    ; no more valid moves, backtrack
    ((null vals) nil)
      ; if number of steps taken equals number of squares on board
      ; then we're done
      ((equal (+ steps 1) (* m_row m_col)) 
        ; increment number of steps, add new visited square
        (setq steps (+ steps 1)) 
        (setq visited-list (append visited-list (list (car vals)))) 
        ; return t 
        ; else continue moving until end
        ; increment steps and add to visited-list 
        (setq steps (+ steps 1)) 
        (setq visited-list (append visited-list (list (car vals)))) 
          ; recurse down, return t if recurse_down found solution
          ((recurse_down m_row m_col) t)
            ; if recurse_down did not find solution, backtrack, removing
            ; moves from visited-list and from "steps" as we backtrack
            ; and then recurse_across
            (setq steps (- steps 1))
            (setq visited-list (reverse (cdr (reverse visited-list))))
            (recurse_across (cdr vals) m_row m_col))))))) ) 

;find the knights tour given board size of (m_row m_col) and 
;starting position (row col)
;use herustics
;function find-knights-tour(number:m_row number:m_col number:row number:col) :
;       ((number number) (number number) )
(defun find-knights-tour (m_row m_col row col)
  ; set the global variables
  (setq visited-list (list (list row col)))
  (setq steps 1)
  ; start searching...
    ((recurse_down m_row m_col) visited-list)
    (t nil)) )

Network Timeouts in C

Reccently, while coding up some P2P sharing software for class, I came across a problem that really got me stuck. (Note, that I forked different processes to handle each upload and upload.) When reading data from another peer, my peer would generally have to block until the other peer responded, since with network programming we can never expect all of our requests to return immediately. The problem was that occassionally, the other peer would decide to die entirely and I was left with a process that would block essentially forever since the signal it was waiting for was never going to come. Now the great thing about blocking reads is that they don't burn CPU time spinning around in a circle waiting for data to arrive, but they do take up space in the process table and in memory. And of course, if my blocked reading proccesses stayed around forever, it would be very simple for a malacious peer to bring my OS to a grinding halt. Essentially, what I needed was a way to make read() timeout. Now anyone vaguely familar with using internet browsers and other such network-reliant programs are probably familar with timeouts, but I had no idea how to implement it in C.

My first thought, was to use setrlimit(), a Unix function that allows the programmer to set the maximum amount of system resources (CPU time, VM size, created file sizes, etc., for more use "man 2 setrlimit"). When setrlimit() is used to set a maximum amount of CPU time, the process will recieve SIGXCPU when the CPU time soft limit is reached, and then the process is killed when the hard limit is reached. At the time, I was a bit groggy so setrlimit() seemed like a great solution, but of course anyone with half a brain (which I apparently didn't have at the time) will realize that setrlimit() is definetely not the solution to this problem. A blocking process doesn't run and therefore doesn't consume CPU time, so setting a maximum CPU time does pretty much nothing to the blocking process; it'll still keep blocking forever.

After a little bit of trawling the internet, I finally came upon the perfect solution: alarms! When alarm(unsigned int seconds) is called, it will raise SIGALRM after so many seconds, realtime seconds mind you and not CPU seconds consumed by the process, even if the process that called alarm() is blocking. I set the alarm right before I began a read() and used signal() to bind a  signal handler to SIGALRM, so that when the alarm went off my signal handler could gracefully kill the timed-out download process!


Seven-Segment Display in VHDL

I wrote my first VHDL project last night during lab, andgot to see my design come to life when I programmed it into a Spartan3 FPGA. It was a pretty basic program, that changed a seven-segment display (like those old LED screens on old calculators) based on which switches were flipped. The four switches used were a BCD (Binary Encoded Decimal) value, so if the first and fourth switches were on and the second and third switches were off, then the BCD value would be 9 (1001). The seven-segment display would then display the value "9" if the switches were in position 1001. Fairly simple to design and program, but quite fun to play with. My VHDL code is below.

entity seven_segment is

    x3,x2,x1,x0: in std_logic;
    a,b,c,d,e,i,g: out std_logic

end seven_segment;

architecture Behavioral of seven_segment is

    a <= NOT( x1 OR x3 OR (x2 AND x0) OR (NOT(x2) AND NOT(x0)) );
    b <= NOT( NOT(x2) OR x3 OR (x1 AND x0) OR (NOT(x1) AND NOT(x0)) );
    c <= NOT( x3 OR x2 OR x0 OR (NOT(x0) AND NOT(x1)) );
    d <= NOT( x3 OR (NOT(x0) AND NOT(x2)) OR (x1 AND NOT(x0)) OR
        (x1 AND NOT(x2)) OR (x2 AND x0 AND NOT(x1)) );
    e <= NOT( (x1 AND NOT(x0)) OR (NOT(x2) AND NOT(x0)) );
    i <= NOT( x3 OR (NOT(X0) AND NOT(x1)) OR (x2 AND NOT(X0) AND x1) OR
        (x2 AND NOT(x1)) );
    g <= NOT( x3 OR (NOT(x1) AND x2) OR (x1 AND NOT(x0)) OR
        (x1 and NOT(x2)) );

end Behavioral;


Keeping It Clean

Ernest Hemingway once said, "I write one page of masterpiece to ninety one pages of shit...I try to put the shit in the wastebasket." And just like writers, programmers also manage to produce quite a bit of shit. Of course, most programmers are perfectly capable of recognizing when they've created an inelegant function, but because of time restraints and deadlines, they just keep on going. But students that are still learning to program, often have trouble recognizing when code is in desperate need of deletion.

A university-level programming class usually requires students to spend a great deal of time working on projects and homework. So its quite easy, after hours of coding, to become emotionally attached to one's code. Generally, a student programmer will make a mistake in a function or block of code, and so they'll add in a quick little fix. Eventually, after numerous little fixes, their function starts to become a giant, awkward, lumbering behemoth that is still wrong.

The most obvious choice is to simply, as Hemingway so succinctly said, "put the shit in the wastebasket" and start from the beginning. But the student has managed, after hours of labor, to become extremely attached to their hundred lines of awkward code and just can't manage to throw away the terrible result of all their hard labor. I say this because when I was learning to program, I often found myself becoming too attached to my code. On one particular occasion, I spent two days patching up the code for my self-balancing AVL binary tree, which was frankly, a piece of shit. Eventually, I threw my AVL tree class in the garbage, started again from scratch, and recreated a working tree class in a few hours.  If I had only been a little more emotionally detached, I might have realized how stupid I was acting.

In order to keep code clean and effective, student programmers need to learn to stop falling in love with their misshapen code-children; code cannot love you back, so don't waste your time developing emotions for it. Just keep it clean kids, and save the loving for another time.


Dynamically Create a Multidimensional Array

I had a few problems trying to dynamically create and pass a multidimensional array in C++ for my previous programming project. Of course, passing an array by value is rather ridiculous when the array is large, so I had to pass by reference. Now, passing a single dimensional array is really quite simple in C++, you just do the following:

int input_cols;
char *char_array_ptr;
cout << "cols? ";
cin >> input_a;
char_array_ptr = new char[input_cols];
return char_array_ptr;

And hey, you're done. The same thing could pretty much be done in C by using malloc, instead of new. But as I mentioned, I needed to pass a multidimensional array.