<![CDATA[asb: head /dev/brain > /dev/www]]> 2016-10-17T12:01:33+05:30 http://akhilsbehl.github.io/ Octopress <![CDATA[HackerRank: Detecting cycles in a linked list]]> 2016-10-17T11:08:42+05:30 http://akhilsbehl.github.io/blog/2016/10/17/hackerrank-detecting-cycles-in-a-linked-list The idea is to keep a slow traverser (the tortoise) and a fast traverser (the hare). If there are no cycles, eventually, the hare should hit the end of the list. However, if there are cycles, eventually the hare will see something that the tortoise has too which is enough for us to stop traversing.

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

class Node(object):

    def __init__(self, data = None, next_node = None):
        self.data = data
        self.next = next_node


def traverser(head, step):
    at = head
    try:
        for i in range(1, step):
            at = at.next
    except AttributeError:
        raise StopIteration
    if at.next is None:
        raise StopIteration
    yield at.next


def has_cycle(head):
    tortoise = traverser(head, 1)
    hare = traverser(head, 2)
    seen_by_tortoise = set()
    while True:
        try:
            seen_by_tortoise.add(next(tortoise))
            hare_test = next(hare)
        except StopIteration:
            return False
        else:
            if hare_test in seen_by_tortoise:
                return True
]]> <![CDATA[HackerRank: Implementing a queue using two stacks.]]> 2016-10-12T14:48:40+05:30 http://akhilsbehl.github.io/blog/2016/10/12/hackerrank-implementing-a-queue-using-two-stacks The idea is to keep an inbox and outbox using stacks. Here is a simple implementation.

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

class Queue(object):

    def __init__(self):
        self._inbox = Stack()
        self._outbox = Stack()

    def _refill(self):
        if not self._outbox:
            while self._inbox:
                self._outbox.push(self._inbox.pop())

    def peek(self):
        self._refill()
        try:
            return self._outbox.peek()
        except IndexError:
            raise EmptyQueueError()

    def pop(self):
        self._refill()
        try:
            retval = self._outbox.pop()
        except IndexError:
            raise EmptyQueueError()
        else:
            return retval

    def push(self, value):
        self._inbox.push(value)


class Stack():

    def __init__(self, iterable=None):
        self._data = [] if iterable is None else list(iterable)

    def __bool__(self):
        return bool(self._data)

    def peek(self):
        return self._data[-1]

    def pop(self):
        return self._data.pop()

    def push(self, value):
        self._data.append(value)


class EmptyQueueError(BaseException):
    pass
]]> <![CDATA[Training with large files in Torch]]> 2016-09-19T17:50:12+05:30 http://akhilsbehl.github.io/blog/2016/09/19/training-with-large-files-in-torch7 Datasets these days are getting larger and and so is hardware in keeping with Moore’s law. However, Moore’s law applies to population trends. For a given user, budget constraints create a situation where hardware resources increase as a step function. On the other hand, the growth function for datasizes can be approximated with a much smoother exponential. This keeps users typically chasing their own hyper-personal version of big data.

I recently started using lua and torch to learn about neural networks. I wanted to start simple and build a classifier for a kaggle competition. However, the data for this competition is too big for my machine with a measly 16 gigs of RAM. [This used to be a luxury only half a decade ago.]

So, after some digging around on github, I figured how to train with fairly large datasets with stock torch infrastructure and I’m gonna show you how and why it works.

How did you do that?

Hold up, what all did you try?

csv2tensor

The file that I have is 2 gigs on disk. So, my first attempt, obviously, was to throw caution to the wind and attempt to load the dataset anyway. To this end, I tried csv2tensor. This was a no-go right from the get-go (you see what I did there?).

This library converts the columns in the data into lua tables and then converts those tables to torch Tensors. The rub is that tables in lua are not allocated in user memory but in the compiler’s memory which has a small upper-bound because in luajit that torch is typically compiled against. This means that using this library will blow up for any dataset which expands to a more than a gig or so.

csvigo

csvigo is the standard library for working with csv files in lua / torch7. Again, my first attempt was to read the whole data into memory with this package. I opened top in a split and proceeded to load the dataset. While this library did not run into the issue above (I think because it uses Tensors directly which are allocated in user-space), it quickly ate up all the available memory and a few gigs of swap before I killed the process. I tried to setdefaulttensortype to torch.FloatTensor which I killed after waiting for under a minute by when it had clocked 7 gigs.

The solution: csvigo with mode=large

At this point, I looked at the csvigo documentation again and found the large-mode option. I decided to try it and was able to successfully put together this solution:

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

local numericData = csvigo.load({
      path = dataDir .. "numeric.csv",
      mode = 'large'
})

-- Use a level of indirection to get at the records
local trainingData = {}

-- Discount 1 for the header row
function trainingData:size() return #numericData - 1 end

--[[
`preprocess` is an arbitrary function that operates on a row of data.
Implement it (or remove it) as per your requirements.
Assumption: The response is at the last index in the record
--]]
setmetatable(trainingData,
            {
                __index = function (tbl, ind)
                   local row = preprocess(numericData[ind + 1])
                   local record = torch.Tensor(row)
                   local response = record[-1]
                   local penultimate = record:size(1) - 1
                   local rest = record[{ {1, penultimate} }]
                   return {rest, response}
                end
});

-- Trainer
----------

-- Let `mlp` be our nn model

local params, gradParams = mlp:getParameters()
local optimState = {learningRate = 1}

-- Training
-----------

local nCols = #(numericData[1]) - 1
local nEpochs = 32
local batchSize = 2048

for epoch = 1, nEpochs do

   local shuffle = torch.randperm(trainingData:size())

   local batch = 1
   for batchOffset = 1, trainingData:size(), batchSize do

      local batchInputs = torch.Tensor(batchSize, nCols)
      local batchResponse = torch.Tensor(batchSize)
      for i = 1, batchSize do
         local thisRecord = trainingData[shuffle[batchOffset + i]]
         batchInputs[i]:copy(thisRecord[1])
         batchResponse[i] = thisRecord[2] + 1
      end

      local function evaluateBatch(params)
         gradParams:zero()
         local batchEstimate = mlp:forward(batchInputs)
         local batchLoss = criterion:forward(batchEstimate, batchResponse)
         local nablaLossOutput = criterion:backward(
            batchEstimate, batchResponse)
         mlp:backward(batchInputs, nablaLossOutput)
         print('Finished epoch: ' .. epoch .. ', batch: ' ..
                  batch .. ', with loss: ' .. batchLoss)
         return batchLoss, gradParams
      end

      optim.sgd(evaluateBatch, params, optimState)

      batch = batch + 1
      batchOffset = batchOffset + batchSize

   end

end

With this method I was able to use the dataset with only two gigs of memory allocated to the process. Perhaps, in another post I will benchmark the performance penalty for doing this when you do have sufficient RAM. I have also not figured out how this will need to be adapted to GPUs. But this is definitely better compared to the option of not using a moderately large dataset at all.

What’s the magic sauce? o.O

Note how the documentation modestly states that the efficiency is under the hood? Which is why we need to use the source, Luke. So, let’s look at this (incomplete) code snippet and comprehend:

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

function Csv:largereadall()
    local ok = pcall(require, 'torch')
    if not ok then
        error('large mode needs the torch package')
    end
    local libcsvigo = require 'libcsvigo'
    local ffi = require 'ffi'
    local path = self.filepath
    local f = torch.DiskFile(path, 'r'):binary()
    f:seekEnd()
    local length = f:position() - 1
    f:seek(1)
    local data = f:readChar(length)
    f:close()

    -- now that the ByteStorage is constructed,
    -- one has to make a dictionary of [offset, length] pairs of the row.
    -- for efficiency, do one pass to count number of rows,
    -- and another pass to create a LongTensor and fill it
    local lookup = libcsvigo.create_lookup(data)

    local out = {}
    local separator = self.separator

    local function index (tbl, i)
        assert(i, 'index has to be given')
        assert(i > 0 and i <= lookup:size(1), "index out of bounds: " ..  i)
        local line = ffi.string(data:data() + lookup[i][1], lookup[i][2])
        local entry = fromcsv(line, separator)
        return entry
    end

  1. Loading to ByteStorage: The first interesting thing that the code does is to load the file as raw bytes. This is the part of code spanning torch.DiskFile(path, 'r'):binary() to f:close(). The intermediate steps are only to calculate the length of the content in bytes. This makes the data take only as much space in memory as it does on the disk (remember how my 2GB file took only 2 gigs in RAM?).

  2. Calculating the byte offset and the byte length of each new record in the file: The libcsvigo.create_lookup(data) essentially scans the byte representation of the file and records at what offset from the beginning is the first byte of each record. Additionally, it also stores how many bytes are in each record – the byte length. These are stored as pairs in the lookup table.

  3. Accessing the ith record in the file: When it’s time to access the ith row in the file, the function index creates a string by reading in lookup[i][2] number of bytes starting from lookup[i][1]. The fromcsv function then splits this record string into a table by splitting it on the separator and returns it us.

This allows us to load large datasets in memory employing only as much memory as is the size of the file on disk (in bytes) with the additional memory cost of creating the LongTensor lookup table. There is, obviously, the additional CPU cost of processing each record as many times as it is read.

]]> <![CDATA[Toggling buffer-level hooks in Emacs]]> 2016-09-07T18:19:05+05:30 http://akhilsbehl.github.io/blog/2016/09/07/toggling-buffer-level-hooks-in-emacs One of the formats that I like to edit is markdown (yeah, yeah, I know about org-mode, shush!). Another thing that I like to do, when editing markdown, is to preview it in my browser as html. This can be done by exporting the markdown file to html each time the markdown buffer is written to. Now, I like this solution except when I don’t! To generalize the problem, one wants an action to be trigerred, perhaps for a major mode (or not), every time an event happens in a buffer. On the other hand, one also wants this behavior to be togglable at will. For example: convert all tabs to spaces, run a linter, compile a file etc every time an event occurs in the buffer.

The first sub-problem – of triggering the action – is solved easily using Emacs’ various hooks. The second problem is also easily solved using a little lisp. Here’s how.

Triggering an event

Let’s assume I have a lisp function called special-behavior-function handy that knows how to execute the special behavior on a buffer. I’d like to call this every time the even happens, say, I write to the buffer. Here’s how to do that:

1
2
3
4
5

(add-hook 'major-mode-hook ;; plug the appropriate major mode
  (lambda ()
    (add-hook 'special-event-hook ;; plug the appropriate hook
      'special-behavior-function ;; plug the appropriate function
      nil 'local)))

The 'local at the end makes sure that the hook is added local to the buffer. That’s usually a good thing. Change to nil if you don’t like it.

Now, this should be enough to solve the first subproblem. However, what if, sometimes, you want to turn this behavior off? Or having turned it off, you want to turn it back on?

Toggling event-based behavior

To achieve this, we introduce a variable to save our preference, a wrapper function to check against our current preference. and a toggle function to toggle this preference. (All this goes into your .emacs, duh!) All of this is done local to a buffer. This way, you can control the behavior for each buffer separately.

Disclaimer: this answer is inspired from this discussion on SO. ;)

Configuration variable

1

(defvar inhibit-special-behavior t) ;; Change t to nil to keep on by default

Wrapper function

1
2
3

(defun wrap-special-behavior-function () ;; try &rest with apply if you need args
  (unless inhibit-special-behavior
    (special-behavior-function)))

Toggle function

1
2
3
4
5
6
7
8
9
10

(defun toggle-special-behavior ()
  (interactive)
  (let ((this-buffer (current-buffer)))
    (if (buffer-local-value inhibit-special-behavior this-buffer)
      (progn
        (set (make-local-variable 'inhibit-special-behavior) nil)
        (message "special behavior uninhibited."))
      (progn
        (set (make-local-variable 'inhibit-special-behavior) t)
        (message "special behavior inhibited.")))))

Now all you gotta do is either M-x this function when you need it or bind it to a key-sequence. See this and this for the markdown export example that I’m personally using.

]]> <![CDATA[Why you have, in fact, used a neural network!]]> 2016-09-06T17:38:12+05:30 http://akhilsbehl.github.io/blog/2016/09/06/why-you-have-in-fact-used-a-neural-network Have you ever used a logistic regression? Would you like to be able to say you have used a neural network – perhaps in your next interview? Here’s your cheat code.

NB: NFL applies insomuch as you will have to know what we are talking about in this post. This is not a tutorial.

Logistic regression

A lot has been said and is known about the logistic regression. Refer Chapter 11 for a thorough discussion. I’ll attempt a quick recap.

The learning problem is to learn the distribution of a categorical response conditional on a set of covariates , i.e. . For the binary response case, there are two values that can take, e.g. , , etc. Traditionally, one of the two responses is encoded as and the other . As such, the learning problem is transformed to learning which is modeled as a Bernoulli outcome with probability of success parametrized as . From here, one can write the log likelihood under standard assumptions and maximiize it to obtain the parameter estimate . In this set up, we have still not chosen the function . Different forms of give rise to different classifiers. One choice – the logistic regression – chooses to be:

A tale of two interpretations

Logit regression has been reinterpreted in innumerable ways. Heck, even this post is a rehashing of one of these interpretations. For our sake, however, we will examine two interpretations and their equivalence.

Using the log odds-ratio

The standard intepretation coming from econometrics and the (generalized) linear models camp is the log-odds interpretation. In this interpretation, one linearly models the log of odds-ratio:

Note that rearranging this is equivalent to the defintion of given above. However, what is more important for this discussion is to note that can be written as a function composition – – applied on the input vector of covariates () and the parameter vector to be learned (). Here is the logistic function and is the dot product of two vectors.

Using a log-linear model

Another interpretation of a logistic regression is as a log-linear model. The difficulty is that the log-linear method is used to estimate outcomes which have support in whereas we need to model which is a probability distribution with support in [0, 1]. The trick to overcome this is to model – an un-normalized probability for each of the binary outcomes as a log-linear model. The true probability is then realized from by normalizing it over all possible outcomes.

Expnonentiating and summing the two un-normalized probabilities, we get (say) which we use to find a normalized probability distribution:

Note that in this formulation, I use to denote model parameters and not . This is because the parameter estimates are in fact different. Contrast the probability of success across the two interpretations:

This arises out of the fact that the log-linear formulation is over-identified because if we know , we automatically know . The over-identification is resolved by setting which reconciles the two expressions above. See the wiki for an explanation.

Once again, we notice that even this formulation of the logistic regression can be factorized into a function composition where where is the softmax function and is the dot product.

Generalization to the multinomial case with the softmax function

The other advantage to choosing the log-linear formulation is that it is easily generalized to the case of the n-ary categorical variable – equivalent to the multinomial logit case. One can easily replicate the discussion above to derive:

NNs as function composition machinery

The class of neural networks that we are going to use here is the simple feed-forward multi-layer perceptron (MLP). For a quick recap, a MLP is a directed acyclical graph which has each layer fully-connected to the next layer. The simplest MLP will have at least three layers: the input layer (to which the data is fed), an output layer (which outputs the results) and one (or more for deeper architectures) hidden layer. Goodfellow et al. (Ch. 1, p. 5) describe:

A multilayer perceptron is just a mathematical function mapping some set of input values to output values. The function is formed by composing many simpler functions. We can think of each application of a different mathematical function as providing a new representation of the input.

Emphasis added.

In fact, in Figure 1.3, the book provides the MLP graph that represents the log-odds formulation of a logistic regression (as the composition , further decomposing into elementary operations and ).

MLP design of a multinomial logit

Similarly, the log-linear interpretation of the logistic regression model can be used to design an n-ary MLP classifier with the following layers:

  1. Input layer of covariates.
  2. Fully connected hidden layer with n linear units (the function).
  3. Fully connected output layer with a softmax unit (the function).
  • The cost function to be minimized under supervision is the cross-entropy, which it turns out (Goodfellow et al., Ch. 5, pp 131-132), is equivalent to maximizing likelihood of the observed sample.

This here is the blueprint of your cheat code promised in the beginning of the post! ;) See this lecture for a full exposition on this design.

tl;dr

This is the key insight that motivated this article: NNs are arbitrary function composition machinery that can be tuned to learn model parameters. This was illustrated by decomposing the multinomial logistic regression as a (quite shallow, in fact) composition of functions and then re-assembling it as a MLP. Indeed, Bengio (Ch. 2, pp. 15 - 16) summarizes that a diverse set of (machine?) learning techniques such as GLM, kernel machines, decision trees, boosting machines, stacking, and even the human cortex etc. are networks with increasingly complex or deep (à la deep learning) compositions of simple functions.

]]> <![CDATA[Inspecting objects at point with ESS]]> 2016-05-30T13:34:32+05:30 http://akhilsbehl.github.io/blog/2016/05/30/inspecting-objects-at-point-with-ess Somewhere in the second half of last year I switched my primary text editor from Vim to Emacs. Calm down! I use Evil. So, one of my primary languages is R and I was in love with this plugin in Vim. A snippet of my vim config that I used to rely heavily on in Vim was:

1
2
3
4
5
6
7
8
9

map <LocalLeader>nr :call RAction("rownames")<CR>
map <LocalLeader>nc :call RAction("colnames")<CR>
map <LocalLeader>n2 :call RAction("names")<CR>
map <LocalLeader>nn :call RAction("dimnames")<CR>
map <LocalLeader>nd :call RAction("dim")<CR>
map <LocalLeader>nh :call RAction("head")<CR>
map <LocalLeader>nt :call RAction("tail")<CR>
map <LocalLeader>nl :call RAction("length")<CR>
map <LocalLeader>cc :call RAction("class")<CR>

These commands were invented by me after looking at a similar usage pattern in the plugin’s manuals. Being able to inspect objects at point without switching from my editor to the R prompt made me much more productive than when I could not do this. After I switched to Emacs and the mighty ESS for programming in R, replicating this was an explicit TODO in my ESS configuration. Ladies & gentlemen, today I bring you the solution. Drumroll!

The primary idea — ess-command wrapped with popup-tip — came from this blog post of yore and was wielded to magnificent effect by yours truly. (Yes, I’m a megalomaniac, thank you very much.)

Lemme show you teh codez.

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

;;; Show a popup by executing arbitrary commands on object at point.
;;; Inspiration:
;;; blogisticreflections.wordpress.com/2009/10/01/r-object-tooltips-in-ess/

;; emacs.stackexchange.com/questions/696/get-content-of-a-buffer
(defun asb-read-into-string (buffer)
  (with-current-buffer buffer
    (buffer-string)))

(defun asb-ess-R-object-popup (r-func)
  "R-FUNC: The R function to use on the object.
Run R-FUN for object at point, and display results in a popup."
  (let ((objname (current-word))
        (tmpbuf (get-buffer-create "**ess-R-object-popup**")))
    (if objname
        (progn
          (ess-command (concat "class(" objname ")\n") tmpbuf)
          (let ((bs (asb-read-into-string tmpbuf)))
            (if (not(string-match "\(object .* not found\)\|unexpected" bs))
                (progn
                  (ess-command (concat r-func "(" objname ")\n") tmpbuf)
                  (let ((bs (asb-read-into-string tmpbuf)))
                    (popup-tip bs)))))))
  (kill-buffer tmpbuf)))

(defun asb-ess-R-object-popup-str ()
  (interactive)
  (asb-ess-R-object-popup "str"))

(defun asb-ess-R-object-popup-interactive (r-func)
  (interactive "sR function to execute: ")
  (asb-ess-R-object-popup r-func))

(evil-leader/set-key-for-mode 'ess-mode "ei" 'asb-ess-R-object-popup-str)
(evil-leader/set-key-for-mode 'ess-mode "eI"
  'asb-ess-R-object-popup-interactive)

The function asb-ess-R-object-popup allows us to yank the word at point and execute an arbitrary function on it (without arguments) and display the output as a popup-tip. This function is wrapped into asb-ess-R-object-popup-str mapped to <leader>ei (evil-ess-inspect) to inspect the str of the object interactively because this is what I use the most. Another function called asb-ess-R-object-popup-interactive mapped to <leader>eI (evil-ess-interactive-inspect) asks the user what R function to inspect the object with. Common suspects will be head, tail, names, etc. You know the drill. Have a look at the video and pay attention to the minibuffer.

PS: Actually, don’t bother watching the video; I don’t know why youtube insists on downgrading the video quality.

]]> <![CDATA[Python's AST module: Bringing a gun to a knife fight!]]> 2016-05-19T16:22:54+05:30 http://akhilsbehl.github.io/blog/2016/05/19/pythons-ast-module-bringing-a-gun-to-a-knife-fight So, I’ve been writing unit tests for some statistical code using py.test. One of the sweet things about py.test is that it gives you some cute context specific comparison assertions where you can check a data structure with another.

The problem that I ran into is when using this with floating point numbers. A minimal (convoluted) example:

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

>>> import pandas as pd

>>> pd.np.random.seed(3141)
>>> xx = pd.np.random.random(17)

>>> print pd.np.percentile(xx, 25)
0.386739093187

>>> assert 0.386739093187 == pd.np.percentile(xx, 25)
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-16-f6262184b4b6> in <module>()
----> 1 assert 0.386739093187 == pd.np.percentile(xx, 25)

AssertionError:

Now, this is not that annoying unless you wanna do this for complicated data structures such as dicts of lists of floats etc. and you want to use the assertion goodness that comes with py.test. And I had exactly this situation at hand. Disclaimer: Don’t try this at work! Even though I did.

I was thinking that it’d be easy as pie to do this in a lisp by traversing the structure with a lambda that will round all the floats. And then I figured that Python can do this for me using the AST module. There is a good introduction to the module here and a discussion on appropriate things to do with ASTs here.

So, here is what I ended up implementing (this is miles away from being safe to use) to solve the problem.

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

import ast
import codegen

class NumberRounder(ast.NodeTransformer):

    def __init__(self, digits):
        self.digits = digits

    def visit_Num(self, node):
        if isinstance(node.n, float):
            return ast.Num(round(node.n, self.digits))
        return node


def round_numbers_in(literal, digits=2):
    nr = NumberRounder(digits=digits)
    original_ast = ast.parse(str(literal))
    rewritten_ast = nr.visit(original_ast)
    rewritten_source = codegen.to_source(rewritten_ast)
    rewritten_literal = ast.literal_eval(rewritten_source)
    return rewritten_literal

And voila!

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

>>> sample_complicated_literal = {
    'a': {
        'test': {
            'outliers': [0.074264470377902181, 0.83386867290874311],
            'quantiles': {
                'median': 0.090294684490804245,
                'upper_quartile': 0.46208167869977368,
                'lower_quartile': 0.082279577434353213,
                'minimum': 0.075867491789192387,
                'maximum': 0.75951127406694918
            }
        }, 'target': {
            'outliers': [0.90590397810859369, 0.074264470377902181],
            'quantiles': {
                'median': 0.51193055816399746,
                'upper_quartile': 0.83386867290874311,
                'lower_quartile': 0.38673909318708044,
                'minimum': 0.087088641668223832,
                'maximum': 0.90457554405068796
            }
        }
    }, 'c': {
        'test': {
            'outliers': [0.76596994956051723, 0.18885210718343348],
            'quantiles': {
                'median': 0.42025570188230343,
                'upper_quartile': 0.59311282572141033,
                'lower_quartile': 0.30455390453286846,
                'minimum': 0.2119924666533205,
                'maximum': 0.73139852479269585
            }
        }, 'target': {
            'outliers': [0.024942395243662818, 0.90001151823365477],
            'quantiles': {
                'median': 0.42025570188230343,
                'upper_quartile': 0.54953955294935286,
                'lower_quartile': 0.18885210718343348,
                'minimum': 0.057602330989601373,
                'maximum': 0.89242588191298255
            }
        }
    }
}

>>> import pprint

>>> pprint.pprint(round_numbers_in(sample_complicated_literal, digits=4))

{'a': {'target': {'outliers': [0.9059, 0.0743],
                'quantiles': {'lower_quartile': 0.3867,
                                'maximum': 0.9046,
                                'median': 0.5119,
                                'minimum': 0.0871,
                                'upper_quartile': 0.8339}},
    'test': {'outliers': [0.0743, 0.8339],
                'quantiles': {'lower_quartile': 0.0823,
                            'maximum': 0.7595,
                            'median': 0.0903,
                            'minimum': 0.0759,
                            'upper_quartile': 0.4621}}},
'c': {'target': {'outliers': [0.0249, 0.9],
                'quantiles': {'lower_quartile': 0.1889,
                                'maximum': 0.8924,
                                'median': 0.4203,
                                'minimum': 0.0576,
                                'upper_quartile': 0.5495}},
    'test': {'outliers': [0.766, 0.1889],
                'quantiles': {'lower_quartile': 0.3046,
                            'maximum': 0.7314,
                            'median': 0.4203,
                            'minimum': 0.212,
                            'upper_quartile': 0.5931}}}}
]]> <![CDATA[Boggle solver: Linear and recursive search]]> 2015-02-14T15:03:17+05:30 http://akhilsbehl.github.io/blog/2015/02/14/boggle-solver-linear-and-recursive-search I was recently introduced to a Boggle solver problem by a friend of mine. Put simply, given a boggle board of sixteen characters and a dictionary, the program needs to figure out how many words from the dictionary are possible on the boggle board. The one deviation from standard boggle is that adjacent moves restriction is relaxed, i.e. order is unimportant.

My repository on Github discusses the problem and the two solutions implemented and their tradeoffs in much more detail along with presenting the code. Do visit.

]]> <![CDATA[`timeit` macro for SBCL]]> 2014-12-25T05:23:28+05:30 http://akhilsbehl.github.io/blog/2014/12/25/timeit-macro-for-sbcl I am the sort of person who really likes to know how much time code I have written takes to run. I believe that it is important to know what works in your language and what does not and what sort of efficiency trade offs need to be made for expressiveness and brevity. Since, I am learning common lisp a little seriously again, I have been interested in seeing how to profile code in it. Even though I haven’t reached this far that I have started using the statistical CPU profiler or the statistical allocation profiler, I am starting out with simply being able to time code I write quickly.

Since, writing macros in lisp is so easy and timing code is just the sort of thing macros are really useful for, I decided to practice some macro writing to write a timeit macro. Similar attempts have been made in the past but I wanted to roll my own. After some struggle and a little nudge I was able to write something satisfactory:

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

(defmacro timeit ((&key
                    (to-stream *standard-output*)
                    (with-runs 1))
                  &body body)
  "Note that this function may barf if you are depending on a single evaluation
  and choose with-runs to be greater than one. But I guess that will be the
  caller's mistake instead."
  (let ((start-time (gensym))
        (stop-time (gensym))
        (temp (gensym))
        (retval (gensym))
        (elapsed-time (gensym)))
    `(let* ((,start-time (get-internal-run-time))
            (,retval (let ((,temp))
                       (dotimes (i ,with-runs ,temp)
                         (setf ,temp ,@body))))
            (,stop-time (get-internal-run-time))
            (,elapsed-time (/ (- ,stop-time ,start-time)
                              internal-time-units-per-second)))
       (format ,to-stream
               (concatenate 'string
                            "~CAverage (total) time spent in expression"
                            " over ~:d iterations: ~f (~f) seconds.~C")
               #\linefeed
               ,with-runs
               ,elapsed-time
               (/ ,elapsed-time ,with-runs)
               #\linefeed)
       ,retval)))

Hopefully, this is useful for someone not in the mood to write their own code to do this. This was definitely useful for me to write.

]]> <![CDATA[R: Converting simple_triplet_matrix to other sparse matrix formats.]]> 2014-11-21T14:17:11+05:30 http://akhilsbehl.github.io/blog/2014/11/21/r-converting-simple-triplet-matrix-to-other-sparse-matrix-formats When working with the tm package in R, it produces a DocumentTermMatrix or TermDocumentMatrix as an S3 object of class simple_triplet_matrix from the package slam. Now R has various different packages for creating sparse matrices, each of which have packages depending upon themselves. Long back when working with text data I had created two functions to convert a simple_triplet_matrix to a matrix of class sparseMatrix (package: Matrix) and that to a matrix of class matrix.csr (package: SparseM). The conversions are simple enough once you have read through the documentation of the three packages but hopefully this will save someone some time.

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

asSparseMatrix = function (simpleTripletMatrix) {
  retVal = sparseMatrix(i=simpleTripletMatrix[["i"]],
                        j=simpleTripletMatrix[["j"]],
                        x=simpleTripletMatrix[["v"]],
                        dims=c(simpleTripletMatrix[["nrow"]],
                               simpleTripletMatrix[["ncol"]]))
  if (!is.null(simpleTripletMatrix[["dimnames"]]))
    dimnames(retVal) = simpleTripletMatrix[["dimnames"]]
  return(retVal)
}

asMatrixCSR = function (sparseMatrix) {
  warning("Will lose dimnames!")
  as.matrix.csr(new("matrix.csc",
                    ra=sparseMatrix@x,
                    ja=sparseMatrix@i + 1L,
                    ia=sparseMatrix@p + 1L,
                    dimension=sparseMatrix@Dim))
}
]]> <![CDATA[R: Converting a data.table to a multi way array (cube)]]> 2014-08-20T15:42:00+05:30 http://akhilsbehl.github.io/blog/2014/08/20/r-converting-a-data-dot-table-to-a-multi-way-array-cube This post discusses the problem of converting a data.table to the array data structure in R. The idea is analogous to converting a denormalized dataset that presents both dimensions and facts in a table as columns of the table to a completely normalized fact cube along the dimensions of the dataset.

The problem can be solved in multiple ways in R with attending constraints of these approaches – e.g. plyr::daply, xtabs, by or a manual home-brewn set of split and lapply routine. Without discussing the constraints I observed with the existing techniques, I am presenting an alternative approach here that depends on unrolling the rectangular data structure into a linear structure and then reshaping it by manually counting the facts and dimension sizes (think strides). The choice of using a data.table was purely for efficiency reasons but the same idea can be implemented with a data.frame with little changes to the code.

Dislcaimer: A constraint (I see it as essentially the functionality being implemented here) that all rows should be unique along the chosen dimensions. Since a cube must have all dimensions perfectly normalized.

Following is the implemenation with an example:

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

dt2array = function (x, facts, dims) {
  stopifnot(is.data.table(x))
  setkeyv(x, rev(dims))
  stopifnot(!any(duplicated(x)))
  dimensions = lapply(x[ , rev(dims), with=FALSE],
                      function (x) sort(unique(x)))
  xFull = data.table(expand.grid(dimensions, stringsAsFactors=FALSE))
  setkeyv(xFull, rev(dims))
  x = data.table:::merge.data.table(xFull, x, by=dims, all=TRUE)
  factsVec = unlist(x[ , facts, with=FALSE], recursive=FALSE, use.names=FALSE)
  nFacts = length(facts)
  nDims = length(dims)
  if (nFacts > 1) {
    dim(factsVec) = c(sapply(dimensions, length), nFacts)
    dimnames(factsVec) = c(dimensions, "facts"=list(facts))
    return(aperm(factsVec, perm=c(nDims:1, nDims + 1)))
  } else {
    dim(factsVec) = sapply(dimensions, length)
    dimnames(factsVec) = dimensions
    return(aperm(factsVec))
  }
}

dat = data.table(f1=runif(10),
                 f2=runif(10),
                 f3=runif(10),
                 d1=letters[1:5],
                 d2=rep(letters[3:4], each=5),
                 d3=LETTERS[1:2])
dt2array(dat, "f1", c("d1", "d2", "d3"))
dt2array(dat, c("f1", "f2"), c("d1", "d2", "d3"))
dt2array(dat, c("f1", "f2", "f3"), c("d1", "d2", "d3"))

The implementation is very fast, if I say so myself, since almost all manipulations being used here are fairly low-level in R implemented in C. Hopefully, this will be useful.

]]> <![CDATA[Knuth-Fisher-Yates shuffling algorithm]]> 2014-08-18T21:41:08+05:30 http://akhilsbehl.github.io/blog/2014/08/18/knuth-fisher-yates-shuffling-algorithm So, yesterday, I was sent this article by a friend. Articles titled X every developer should know sort of titles pique my interest very much. So, I headed over to this article only to find myself too confused. What I found more confusing is that the article links to one of Jeff Atwood’s blogposts that discusses the same concept.

The central idea of the post is to correct a naive implementation of a shuffling algorithm. My confusion arose from the fact that after reading the article, I could only think that the algorithm was blatantly incorrect and not naive. The differences between the two algorithms – the naive one and the one ascribed to Knuth, Fisher, & Yates is what, in sampling 101, is between sampling with replacement and sampling without replacement. This quote essentially highlights the naivete indeed:

How do we know that that above algorithm is biased? On the surface it seems reasonable, and certainly does some shuffling of the items.

Some shuffling does not mean a random permutation at all. This is akin to saying a naive implementation of a queue sometimes inserts incoming items at the head of the queue.

Another shuffling algorithm?

On the other hand, what was fruitful was that the article reminded me of a shuffling algorithm I recently wrote to solve problem number 25 of 99 Lisp Problems. The minor difference between the two algorithms is that the lisp algorithm pops an element from the original array per turn and collects it in a new array which becomes a random permutation (shuffle) of the original array at the end. The KFY algorithm instead swaps two elements at each turn. It can be worked out that, mathematically, the two algorithms are identical. But the KFY algorithm saves you making a copy. Therefore, yes, KFY is an algorithm that every programmer should know. Additionally, every programmer should also know the standard library of their language.

]]> <![CDATA[Editing markdown in Vim and previewing in Firefox.]]> 2014-08-17T15:03:15+05:30 http://akhilsbehl.github.io/blog/2014/08/17/editing-markdown-in-vim-and-previewing-in-firefox Lately, I have taken to maintaining most of my text in Markdown (desperately trying to avoid Emacs’ org-mode) and previewing it while editing in Vim is something that is a nice to have. So I searched a little bit and found this nice little snippet by Ellen Gummesson that I then adapted per my preferences as such:

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

" Preview markdown in Firefox

function! PreviewMarkdown()
  let outFile = expand('%:r') . '.html'
  silent execute '!cd %:p:h'
  silent execute '!python -m markdown % >' . outFile
  " The screen will need to be redrawn. Dunno why! :\
  silent execute 'redraw!'
endfunction

augroup markdown
    au!
    au BufNewFile,BufRead *.md,*.markdown setlocal filetype=ghmarkdown
    au BufNewFile,BufRead *.md,*.markdown setlocal textwidth=0
    autocmd FileType ghmarkdown map <LocalLeader>p
          \ :call PreviewMarkdown()<CR>
augroup END
]]> <![CDATA[Send Python commands from Vim to IPython via tmux.]]> 2014-08-17T13:58:53+05:30 http://akhilsbehl.github.io/blog/2014/08/17/send-python-commands-from-vim-to-ipython-via-tmux A few days ago I built a very simple framework (bunch of vimscript commands really) to work with vim and IPython along the lines of the Vim-R-Plugin. In this post I show what I had to do to get this to work.

Detour: Vim R Plugin

If you live in Vim and work with R (or hope / want to) there is no better tool to boost your producitivity than the marriage of these two tools as brought about in the Vim R Plugin. R was my first serious programming language (horror of horrors!) and I had gotten sold on the Vim R Plugin model of doing things very early on. The plugin provides you the whole shebang like any modern IDE such as syntax highlighting, completion based on namespaces and R environments, an object browser that opens in Vim.

However, I don’t use any of that fancy stuff. I tend to think of myself as a simple man with simple needs. The only thing I use the plugin to do is to send commands from Vim to R. Additionally, I wrote my own wrappers to execute my most frequent actions on R objects under the cursor in Vim. This makes me feel like I am always in the R console even when I am in Vim. And this is just the fluency I wanted in IPython with Vim. No bells and whistles, just make me feel like my editor understands my console and that is it.

Here is the chunk from my .vimrc that is relevant for this plugin. Even if you are not as minimalistic as I am, you may yet find the ideas in these snippets useful:

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

" Custom commands.
map <LocalLeader>nr :call RAction("rownames")<CR>
map <LocalLeader>nc :call RAction("colnames")<CR>
map <LocalLeader>n2 :call RAction("names")<CR>
map <LocalLeader>nn :call RAction("dimnames")<CR>
map <LocalLeader>nd :call RAction("dim")<CR>
map <LocalLeader>nh :call RAction("head")<CR>
map <LocalLeader>nt :call RAction("tail")<CR>
map <LocalLeader>nl :call RAction("length")<CR>
map <LocalLeader>cc :call RAction("class")<CR>
map <LocalLeader>nw :call SendCmdToR("system('clear')")<CR>
map <LocalLeader>ne :call SendCmdToR("system('traceback()')")<CR>
map <LocalLeader>sb :call SendCmdToR("system.time({")<CR>
map <LocalLeader>se :call SendCmdToR("})")<CR>
map <LocalLeader>tt :call SendCmdToR("tt = ")<CR>

The RAction commands work this way: vim will inspect the word under the cursor and call the specified command with that argument. For example, ,nr (my LocalLeader gets mapped to ,) gives me the rownames of whichever object I happen to be sitting at and so on.

The SendCmdToR commands are slightly different. These can be used to send arbitrary text to the R console. The last two are the most interesting to me. Whenever I want to time some arbitrary set of commands I would say ,sb (system.time begin) which would start a system.time({ expression block on my console. Then I send whichever R commands I want to time to the console and finish with ,se (system.time end) which will finish my expression and time it.

A lot of times when debugging R code I want to evaluate chunks of the body of my function / code into a temporary variable (tt by convention). The plugin allows me to send arbitrary visual selections from vim to R. Therefore, often I would say ,tt to start a variable assignment expression and then send whatever chunk I want to evaluate to tt by selecting it visually and executing it.

Working with IPython and Vim

I had been looking for a plugin which provides me a similar model for IPython since a long time to no avail. Things that I found either did too many things or did them too differently. I was making do with %paste from IPython for a long time. Even though that was usable, it always made the distinction between my editor and my console too painfully obvious. And then I revisited one of the plugins that I have known for a long time but never investigated in detail.

The Screen plugin is a mighty lightweight and simple plugin (something that I already had as a dependency for – wait for it – Vim R Plugin) that allows you to send arbitrary commands from Vim running in a tmux split to an arbitrary console (think shell, lisp, ruby, whatever you want it to be). An hour of RTFM and experimentation later I had hacked out a simple usable framework. This is a preview of that. I am pretty sure I will hack it to make this more usable over time (perhaps to match my muscle memory for the Vim R Plugin). All changes should get reflected in my vimrc here.

This is the first time I wrote any serious VimScript. I know this is kludgy but please bear with me.

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

" ervandew/screen configuration to send commands to ipython.

let g:ScreenImpl = "Tmux"

" Open an ipython3 shell.
autocmd FileType python map <LocalLeader>p :ScreenShell! ipython3<CR>

" Open an ipython2 shell.
autocmd FileType python map <LocalLeader>pp :ScreenShell! ipython2<CR>

" Close whichever shell is running.
autocmd FileType python map <LocalLeader>q :ScreenQuit<CR>

" Send current line to python and move to next line.
autocmd FileType python map <LocalLeader>r V:ScreenSend<CR>j

" Send visual selection to python and move to next line.
autocmd FileType python map <LocalLeader>v :ScreenSend<CR>`>0j

" Send a carriage return line to python.
autocmd FileType python map <LocalLeader>a :call g:ScreenShellSend("\r")<CR>

" Clear screen.
autocmd FileType python map <LocalLeader>L
      \ :call g:ScreenShellSend('!clear')<CR>

" Start a time block to execute code in.
autocmd FileType python map <LocalLeader>t
      \ :call g:ScreenShellSend('%%time')<CR>

" Start a timeit block to execute code in.
autocmd FileType python map <LocalLeader>tt
      \ :call g:ScreenShellSend('%%timeit')<CR>

" Start a debugger repl to execute code in.
autocmd FileType python map <LocalLeader>db
      \ :call g:ScreenShellSend('%%debug')<CR>

" Start a profiling block to execute code in.
autocmd FileType python map <LocalLeader>pr
      \ :call g:ScreenShellSend('%%prun')<CR>

" Print the current working directory.
autocmd FileType python map <LocalLeader>gw
      \ :call g:ScreenShellSend('!pwd')<CR>

" Set working directory to current file's folder.
function SetWD()
  let wd = '!cd ' . expand('%:p:h')
  :call g:ScreenShellSend(wd)
endfunction
autocmd FileType python map <LocalLeader>sw :call SetWD()<CR>

" Get ipython help for word under cursor. Complement it with Shift + K.
function GetHelp()
  let w = expand("<cword>") . "??"
  :call g:ScreenShellSend(w)
endfunction
autocmd FileType python map <LocalLeader>h :call GetHelp()<CR>

" Get `dir` help for word under cursor.
function GetDir()
  let w = "dir(" . expand("<cword>") . ")"
  :call g:ScreenShellSend(w)
endfunction
autocmd FileType python map <LocalLeader>d :call GetDir()<CR>

" Get `dir` help for word under cursor.
function GetLen()
  let w = "len(" . expand("<cword>") . ")"
  :call g:ScreenShellSend(w)
endfunction
autocmd FileType python map <LocalLeader>l :call GetLen()<CR>

The ,,a command to send just a carriage return is to complete an indented block when python expects an empty line, e.g. at the end of a for loop.

This opens the possibility of having a bunch of different languages that vim can understand and I can transfer my muscle memory to. I am quite excited.

]]> <![CDATA[Machines that make music and steal jobs]]> 2014-08-17T13:40:17+05:30 http://akhilsbehl.github.io/blog/2014/08/17/machines-that-make-music-and-steal-jobs I stumbled upon two different videos today while surfing the web both of which impressed me deeply. It was only later that I connected the dots between the two. The first is a breathtaking example of what human ingenuity and creativity can achieve with machines; the other a luddite damnation of the same phenomenon. I will put these here and refrain from any comments.

Digitopoly provides a counter-arguments to the conclusions of the second video which I, personally, found unconvincing in their depth of analysis.

]]> <![CDATA[99 LISP problems: Problem #34]]> 2014-08-06T03:23:34+05:30 http://akhilsbehl.github.io/blog/2014/08/06/99-lisp-problems-problem-number-34 Solution to the 99 LISP Problems #34

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

(defun range (lo hi)
    (cond ((> lo hi) nil)
    (t (cons lo (range (1+ lo) hi)))))

(defun eucgcd (m n)
    (let ((p (abs m)) (q (abs n)))
        (cond ((= m n) m)
        (t (gcd (- (max m n) (min m n)) (min m n))))))

(defun coprimep (m n)
    (= (eucgcd m n) 1))

(defun totient (m)
  (cond ((= m 1) 1)
        (t (apply #'+ (mapcar
                        (lambda (x) (if (coprimep m x) 1 0))
                        (range 1 (1- m)))))))

Lisp dialect: Steel Bank Common Lisp

]]> <![CDATA[99 LISP problems: Problem #31]]> 2014-08-06T02:11:59+05:30 http://akhilsbehl.github.io/blog/2014/08/06/99-lisp-problems-problem-number-31 Solution to the 99 LISP Problems #31

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

(defun range (lo hi)
  (cond ((> lo hi) nil)
        (t (cons lo (range (1+ lo) hi)))))

(defun all (alist)
  (cond ((null alist) t)
        (t (and (car alist)
                (all (cdr alist))))))

(defun primep (n)
  (all (mapcar
         (lambda (x) (not (= 0 (mod n x))))
         (range 2 (isqrt n)))))

Lisp dialect: Steel Bank Common Lisp

]]> <![CDATA[99 LISP problems: Problem #33]]> 2014-08-06T02:08:27+05:30 http://akhilsbehl.github.io/blog/2014/08/06/99-lisp-problems-problem-number-33 Solution to the 99 LISP Problems #33

1
2
3
4
5
6
7

(defun eucgcd (m n)
  (let ((p (abs m)) (q (abs n)))
    (cond ((= m n) m)
    (t (gcd (- (max m n) (min m n)) (min m n))))))

(defun coprimep (m n)
  (= (eucgcd m n) 1))

Lisp dialect: Steel Bank Common Lisp

]]> <![CDATA[99 LISP problems: Problem #32]]> 2014-08-06T01:43:25+05:30 http://akhilsbehl.github.io/blog/2014/08/06/99-lisp-problems-problem-number-32 Solution to the 99 LISP Problems #32

1
2
3
4

(defun eucgcd (m n)
  (cond ((or (<= m 1) (<= n 1)) nil)
        ((= m n) m)
        (t (gcd (- (max m n) (min m n)) (min m n)))))

Lisp dialect: Steel Bank Common Lisp

]]> <![CDATA[Julia - Project Euler Qs 1 - 10]]> 2014-07-13T23:51:33+05:30 http://akhilsbehl.github.io/blog/2014/07/13/julia-project-euler-qs-1-10 So, today I decided to take Julia for a spin because, finally, it has a stable version available in the Arch community repo. I tried it with the Project Euler problems to get started. Here is a bunch of code in Julia that solves problems 1 - 10 of Project Euler. I have been watching a lot of videos on the language. I will probably follow up with a post on initial thoughts about the language.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183

########
#  Q1  #
########

i = 1
mysum = 0
while i < 1000
  if (i % 3 == 0) || (i % 5 == 0)
    mysum += i
  end
  i += 1
end
mysum

########
#  Q2  #
########

penultimateFib = 1
ultimateFib = 2
mysum = 2
while (thisFib = penultimateFib + ultimateFib) <= 4e6
  if thisFib % 2 == 0
    mysum += thisFib
  end
  penultimateFib = ultimateFib
  ultimateFib = thisFib
end
mysum

########
#  Q3  #
########

function primep (n)
  retval = true
  for i in 2:isqrt(n)
    if n % i == 0
      retval = false
      break
    end
  end
  return(retval)
end

function nextprime(n)
  n += 1
  while (!primep(n))
    n += 1
  end
  return(n)
end

function previousprime(n)
  if n < 2
    return(2)
  end
  n -= 1
  while (!primep(n) && n > 2)
    n -= 1
  end
  return(n)
end

function primesupto(n)
  # Implements the Eratosthenes' sieve.
  sieve = repeat([true], inner=[n])
  sieve[1] = false
  for i in 2:isqrt(n)
    if sieve[i]
      sieve[2i:i:end] = false
    end
  end
  retval = Int64[]
  for i in 1:n
    if sieve[i]
      Base.push!(retval, i)
    end
  end
  return(retval)
end

# Should not be upto isqrt(n). But works for this case.
n = 600851475143
for p in reverse(primesupto(isqrt(n)))
  if n % p == 0
    println(p)
    break
  end
end

########
#  Q4  #
########

function palindromep(n)
  sn = string(n)
  return(sn == reverse(sn))
end

largest = 0
for i = 101:1:999
  for j = 101:1:999
    n = i * j
    if palindromep(n) && n > largest
      largest = n
    end
  end
end
largest

########
#  Q5  #
########

found = false
i = 380
while !found
  found = true
  i += 380
  for d in 20:-1:11
    if i % d != 0
      found = false
    end
  end
end
i

# Alternatively:
lcm([i for i in 1:20])

########
#  Q6  #
########

mysum = 0
mysumsq = 0
for i in 1:100
  mysum += i
  mysumsq += i^2
end
mysum^2 - mysumsq

########
#  Q7  #
########

i = 1
p = 2
while (i < 10001)
  p = nextprime(p)
  i += 1
end
p

########
#  Q8  #
########

num="7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"

largest = 0
for start in 1:(length(num) - 13)
  seqn = num[start:(start + 12)]
  product = prod([int(i) - 48 for i in seqn])
  if product > largest
    largest = product
  end
end
largest

########
#  Q9  #
########

# sum(25 * (8, 15, 17)) = 1000
prod([25 * i for i in [8, 15, 17]])

#########
#  Q10  #
#########

sum(primesupto(2000000 - 1))
]]>