Monday, April 25, 2016

widths of binary tree

Use backtracking. Used here.
width(n):
    if n == null:
        return 0
    leftwidth, rightwidth = widths(n, 0)
    return -leftwidth + 1 + rightwidth

widths(n, offset = 0):
    if n == null:
        return 0, 0
    lw_l, rw_l = widths(n.left, offset -1)
    lw_r, rw_r = widths(n.right, offset +1)
    leftwidth = min(lw_l, lw_r, offset)  // min of left widths, offset
    rightwidth = max(rw_l, rw_r, offset) // max of right widths, offset
    return leftwidth, rightwidth

Thursday, March 31, 2016

integer or day suffix (ordinal indicator)

Suffixes as th, st, nd, rd.
(n):
    n = abs(n)
    d21 = n % 100
    switch d21:
        case 11:
        case 12:
        case 13:
            return "th"
    d1 = n % 10
    switch d1:
        case 1:
            return "st"
        case 2:
            return "nd"
        case 3:
            return "rd"
        default:
            return "th"
This is a bit faster.
suffixmap = new map() {
    {11, "th"},
    {12, "th"},
    {13, "th"},
    { 1, "st"},
    { 2, "nd"},
    { 3, "rd"}
    }

(n):
    n = abs(n)
    d21 = n % 100
    if suffixmap.has(d21):
        return suffixmap[d21]
    d1 = n % 10
    if suffixmap.has(d1):
        return suffixmap[d1]
    return "th"

Tuesday, March 29, 2016

staque, a stack+queue combo data structure

staque:
    a
    count = start = end = 0
    staque(capacity):
        a = new [capacity]

    push(x):
        if isfull():
            throw
        a[end] = x
        count++
        end = mod(end+1, a.length())
    pop(x):
        if isempty():
            throw
        end = mod(end-1, a.length())
        count--
        return a[end]
    enqueue(x):
        if isfull():
            throw
        a[end] = x
        count++
        end = mod(end+1, a.length())
    x dequeue():
        if isempty():
            throw
        x = a[start]
        start = mod(start+1, a.length())
        count--
        return x
    isempty():
        return count == 0
    isfull():
        return count == a.length()
    
    top():
        if isempty():
            throw
        return a[end]
    start():
        if isempty():
            throw
        return a[start]
    end():
        if isempty():
            throw
        return a[end]
    
    mod(x, n):
        m = x % n
        if m < 0:
            m += n
        return m

Wednesday, March 16, 2016

dijkstra's, a-star algorithm

Finds shortest path (path with min distance) from a node to a particular node or all nodes.

Start from the start node. Pick the node with lowest distance and update distance to its neighbors. Break out early to find min distance to end node only.
graph:

s 4 e
1   1
a 1 b

order of nodes: s, a, b, e
path: s, e (d = 3)

graph:

  1 a 9
s 2 b 7 e

order of nodes: s, a, b, e
path: s, b, e (d = 9)
graph:
    nodes
node:
    id
    neighbors

// O(vlogv + e)
dijkstra(g, start, end):
    dist = new map()
    dist[start.id] = 0
    previous = new map()
    unvisited = new min-heap(capacity: g.nodes.count(), x => x.dist[x.n.id])
    for n in g.nodes:
        unvisited.insert({n, dist})
    while !unvisited.isempty():
        n = unvisited.delete()
        //break early to find min distance to end only
        if n == end:
            break
        for neighbor in n.neighbors:
            //no need to update dist if neighbor is visited
            if !unvisited.has(neighbor.id):
                continue
            distneighbor = n.distance-to(neighbor) + dist[n.id]
            if dist[neighbor.id] == null || distneighbor < dist[neighbor.id]:
                dist[neighbor.id] = distneighbor
                previous[neighbor.id] = n
    if previous[end.id] == null:
        return null //no path
    path = new stack()
    path.push(end.id)
    n = end
    while n.id != start.id:
        n = previous[n.id]
        path.push(n)
    return tuple(dist[end.id], path))

For A*, don't update the neighbor's distance if not within limit. If no path exists within limit then n's distance will be null (infinity).
// O(vlogv + e)
a-star(g, start, end, limit):
    dist = new map()
    dist[start.id] = 0
    previous = new map()
    unvisited = new min-heap(capacity: g.nodes.count(), x => x.dist[x.n.id])
    for n in g.nodes:
        unvisited.insert({n, dist})
    while !unvisited.isempty():
        n = unvisited.delete()
        //no path exists within limit
        if dist[n.id] == null:
            break
        //break early to find min distance to end only
        if n == end:
            break
        for neighbor in n.neighbors:
            //no need to update dist if neighbor is visited
            if !unvisited.has(neighbor.id):
                continue
            distneighbor = n.distance-to(neighbor) + dist[n.id]
            if (dist[neighbor.id] == null || distneighbor < dist[neighbor.id])
                && distneighbor <= limit:
                dist[neighbor.id] = distneighbor
                previous[neighbor.id] = n
    if previous[end.id] == null:
        return null //no path
    path = new stack()
    path.push(end.id)
    n = end
    while n.id != start.id:
        n = previous[n.id]
        path.push(n)
    return tuple(dist[end.id], path))
[Hat tip to SM]

Wednesday, February 03, 2016

compress string

Corner case: If s has digits, return itself.
compress(s):
    if s == null:
        throw "null"
    for i = 0, i < s.length(), i++:
        if 0 <= (s[i] - '0') <= 9:
            return s
    start = end = 0
    buffer = new
    while start < s.length():
        while end < s.length() && s[end] == s[start]:
            end++
        length = end - start
        buffer.append(s[start] + length)
        start = end
    return buffer.length() >= s.length() ? s : buffer.tostring()
[Hat tip to SE]

Sunday, August 30, 2015

if integer is palindrome

(n):
    if n < 0:
        n = -n
    digits = new (capacity: 10) // int.max
    while n > 0:
        digit = n %10
        n = n /10
        digits.add(digit)
    result = true
    start = 0
    end = digits.length - 1
    while start < end:
        if digits[start] != digits[end]
            result = false
            break
        start++
        end--
    return result
[Hat tip to SM]

Friday, August 21, 2015

boggle game

tuple(i, j, direction) boggle(a, word):
    if a == null || word == null:
        throw
    for i = 0, i < a.length, i++:
        if a[i] == null:
            throw
        for j = 0, j < a[i].length, j++:
            // right
            if i+word.length <= a.length: // only check if word fits
                for k = 0, k < word.length, k++:
                    if a[i+k][j] != word[k]:
                        break
                if k == word.length:
                    return tuple(i, j, direction.right)
            // left
            if i-word.length+1 >= 0: // only check if word fits
                for k = 0, k < word.length, k++:
                    if a[i-k][j] != word[k]:
                        break
                if k == word.length:
                    return tuple(i, j, direction.left)
            // down
            if j+word.length <= a.length: // only check if word fits
                for k = 0, k < word.length, k++:
                    if a[i][j+k] != word[k]:
                        break
                if k == word.length:
                    return tuple(i, j, direction.down)
            // up
            if j-word.length+1 >= 0: // only check if word fits
                for k = 0, k < word.length, k++:
                    if a[i][j-k] != word[k]:
                        break
                if k == word.length:
                    return tuple(i, j, direction.up)
    return null
[Hat tip to SM]

Wednesday, August 19, 2015

string.format() modified

Make the below examples work for string.format() method.
"{} is a {meta-for-test}".format("this", "test")
    => "this is a test"
"the name is {last}. {first} {last}.".format("bond", "james")
    => "the name is bond. james bond."
For the built-in string.format(), the below formats work.
string.format("{0} is a {1}",  "this", "test")
    => "this is a test"
string.format("the name is {0}. {1} {0}.",  "bond", "james")
    => "the name is bond. james bond."
The code works by converting the formats into the workable ones and delegating to the built-in string.format() method.
format(format, args):
    buffer = new buffer(format)
    i = 0
    param = 0
    metatoparamMap = new
    while i < buffer.length:
        // stop at { or }
        while i < buffer.length && buffer[i] != '{' && != '}':
            i++
        // no more left
        if i == buffer.length:
            break
        // escaped {{ or }}
        if i +1 < buffer.length && buffer[i] == buffer[i+1]:
            i += 2
            continue
        // } before {
        if buffer[i] == '}':
            break
        start = i
        // stop at }
        while i < buffer.length && buffer[i] != '}':
            i++
        // { not matched
        if i == buffer.length:
            break
        end = i
        // get meta substring
        metastart = metaend = start+1
        // ',' and ':' are special formatting chars
        while buffer[metaend] != '}' && != ',' && != ':':
            metaend++
        meta = buffer.substring(metastart, metaend-metastart)
        increment = true
        // insert param only if meta is not int
        if !int.tryparse(meta):
            buffer.remove(metastart, meta.length)
            metakey = meta.trim()
            // if meta is in meta->paramindex map, reuse the index
            if metatoparamMap.has(metakey):
                paramindex = metatoparamMap[metakey]
                // do not increment param index as reusing
                increment = false
            else:
                paramindex = param.tostring()
                // put in meta->paramindex map
                if metakey != "":
                    metatoparamMap[metakey] = paramindex
            buffer.insert(metastart, paramindex)
            // adjust end as buffer is inserted/removed
            end += -meta.length +paramindex.length
        // increment param even if index is not inserted
        if increment:
            param++
        i = end +1 // i++ does not work
    return string.format(buffer.tostring(), args)

if string is integer

// examples
//true
1
+1
+01
-1
-01
+0
-0
+00
-00
12345678901234567890
-12345678901234567890
//false
+
-
++0
--0
null
""
(s):
    if s == null:
        return false
    s = s.trim()
    if s == "":
        return false
    for i = 0, i < s.length, i++:
        if (s[i] == '+' || s[i] == '-') && i == 0 && i + 1 < s.length:
            continue
        if !(0 <= s[i] - '0' <= 9):
            break
    return i == s.length

Friday, August 14, 2015

get the winning bid and final price

Bid has a price. It may also have an escalation where it goes up to a max price in some increment.

The ibid interface makes the code cleaner.
bid: ibid
    id //int order in which received
    price
    
    id():
        return id
    price():
        return price
    increment():
        return 0
    maxprice():
        return price

escalatingbid: bid, ibid
    increment
    maxprice
    
    increment():
        return increment
    maxprice():
        return maxprice
    
ibid:
    id()
    price()
    increment()
    maxprice()
The bid with the highest maxprice() wins. To calculate the final price, the 2nd highest bid is also required.
//examples

300-325, +2 // 300
275-299, +3

300-325, +2 // 312
275-310, +3

300-325, +2 // 312
275-311, +3

320-325, +2 // 325
320-324, +3

320-325, +2 // 325
300-325, +3

winningbid(ibid[] bids):
    if bids == null:
        throw
    bid1, bid2 = top(bids, 2, new bidcomparer())
    if bid1 == null:
        // no winner
        return null
    if bid2 == null || bid2.maxprice() < bid1.price():
        price = bid1.price()
    else:
        escalation = 
            (((bid2.maxprice() - bid1.price()) / bid1.increment()) + 1)
                * bid1.increment()
        price = bid1.price() + escalation
        if price > bid1.maxprice():
            price = bid1.maxprice()
    return price, bid1
When the maxprice() is same for 2 bids, the bid that came in first wins.
// quick and dirty
top2(bids, comparer):
    if bids == null || comparer == null:
        throw
    max1 = null
    max2 = null
    for bid in bids:
        if max1 == null || comparer.compareto(bid, max1) > 0:
            max2 = max1
            max1 = bid
    return max1, max2

bidcomparer: icomparer{ibid}
    int compareto(bid1, bid2):
        if bid1 == null && bid2 == null:
            return 0
        if bid1 == null:
            return -1
        if bid2 == null:
            return 1
        compare = bid1.maxprice().compareto(bid2.maxprice())
        if compare == 0:
            // when maxprice() is same, pick the one that came first
            compare == -1 * bid1.id().compareto(bid2.id())
        return compare