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 numeric

// examples
//true
1
+1
+01
-1
-01
+0
-0
+00
-00
12345678901234567890
-12345678901234567890
//false
+
-
++0
--0
null
""
(s):
    if s == null || s == "":
        return false
    for i = 0, i < s.length, i++:
        if i == 0 && i + 1 < s.length && (s[i] == '+' || s[i] == '-'):
            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

Thursday, August 13, 2015

all pairs in array that sum to k

//example:
k = 5
a    :  1  3  4  5  6  7  2  2 -1
delta:  4  2  1  0 -1 -2  3  3  6 // delta = k - a[i]

pairs: (1,4), (3,2), (3,2), (6,-1)
// O(n) time, O(n) space
(a, k):
    pairs = new
    set numbers = new // for indexs, use map as ntoi[a[i]] = i
    for i = 0, i < a.length, i++:
        delta = k - a[i]
        if numbers.has(delta):
            pairs.add(tuple(delta, a[i]))
        numbers.add(a[i])
    return pairs

Wednesday, August 12, 2015

derive an unbiased function given a biased one

For f'(),
p(0) = 0.4
p(1) = 0.6

Derive f() such that
p(0) = 0.5
p(1) = 0.5
// probabilities
p(0,0) = 0.4 * 0.4 = 0.16 // discard
p(1,1) = 0.6 * 0.6 = 0.36 // discard
p(0,1) = 0.4 * 0.6 = 0.24 // pick
p(1,0) = 0.6 * 0.4 = 0.24 // pick
//f() is non-deterministic
f():
    while true:
        t = f'()
        if t != f'():
            return t

english phrase for integer

999,999,999,999 -> nine hundred ninety nine billion, nine hundred ninety nine million, nine hundred ninety nine thousand, nine hundred ninety nine.

Divide the number into groups of 3 digits. Each group has a suffix as thousand, million, billion, etc. except the first. Within the group the phrasing is same.
//example
text(n):
    if n > 999,999,999,999:
        throw
    if n == 0:
        return "zero"
    if n < 0:
        return "negative " + text(-n)
    groups = new list()
    while n > 0:
        groups.add(n %1000)
        n = n /1000
    buffer = new
    for i = groups.length-1, i >= 0, i--:
        if groups[i] > 0:
            buffer
                .append(convert3digits(groups[i]))
                .append(suffix(i))
                .append(", ")
    buffer.length -= 2
    return buffer.tostring()

// tests
0
1-9
10-19
20,30,...,90
21,32,...,99
100
101-109
110-119
120,130,...,190
121,132,...,199

convert3digits(n):
    if n < 0 || n > 999:
        throw
    buffer = new
    digit3 = n /100
    if digit3 > 0:
        buffer.append(ntophrasemap[digit3] + " hundred")
    digit21 = n %100
    if digit21 > 0:
        if digit3 > 0:
            buffer.append(" ")
        if ntophrasemap.has(digit21):
            buffer.append(ntophrasemap[digit21])
        else:
            digit1 = digit21 %10
            digit20 = digit21 -digit1
            buffer.append(ntophrasemap[digit20] + " " + ntophrasemap[digit1])
    return buffer.tostring()

suffix(i):
    if i == 0:
        return ""
    if i == 1:
        return " thousand"
    if i == 2:
        return " million"
    if i == 3:
        return " billion"
    throw

ntophrasemap = build-ntophrasemap()

build-ntophrasemap():
    ntophrasemap = {
    // key -> value
         1 -> "one"
         2 -> "two"
         3 -> "three"
         4 -> "four"
         5 -> "five"
         6 -> "six"
         7 -> "seven"
         8 -> "eight"
         9 -> "nine"
        10 -> "ten"
        11 -> "eleven"
        12 -> "twelve"
        13 -> "thirteen"
        14 -> "fourteen"
        15 -> "fifteen"
        16 -> "sixteen"
        17 -> "seventeen"
        18 -> "eighteen"
        19 -> "nineteen"  
        20 -> "twenty"
        30 -> "thirty"
        40 -> "fourty"
        50 -> "fifty"
        60 -> "sixty"
        70 -> "seventy"
        80 -> "eighty"
        90 -> "ninety"
    }
    return ntophrasemap
[Hat tip to ctci]

Monday, August 10, 2015

minimal middle unsorted part of array

Find the minimal middle unsorted part of array which if sorted would make the array sorted.

The array consists of 3 parts left, middle, right. Initially left is the increasing sequence from beginning and right is the decreasing sequence from end. The left and right parts shrink till the following condition is met.
end(left) <= min(middle) && max(middle) <= start(right)
//example
  l        r
134558-58-4889
  |455-58-8|

min:4 max:8

 l   r
123-2
 |2-3|

min:2, max:3

l      r
 4-32-1
|1-23-4|

min:1, max:4
// assume a is increasing
(a):
    // left
    left = leftindex(a)
    // right
    right = rightindex(a)
    // return if already sorted
    if left > right:
        return left+1, right-1
    // min, max
    min, max = minmax(a, left, right)
    // shrink left, right
    left, right = shrink(a, left, right, min, max)
    // return
    return left+1, right-1

leftindex(a):
    left = 0
    while left+1 < a.length && a[left] <= a[left+1]:
        left++
    return left

rightindex(a):
    right = a.length-1
    while right-1 >= 0 && a[right-1] <= a[right]:
        right--
    return right

minmax(a, start, end):
    min = max = a[start]
    for i = start, i <= end, i++:
        if a[i] < min:
            min = a[i]
        if a[i] > max:
            max = a[i]
    return min, max

shrink(a, left, right, min, max):
    while left >= 0 && a[left] > min:
        left--
    while right < a.length && a[right] < max:
        right++
    return left, right
[Hat tip to ctci]

max of two integers, no compare operator or if else

Use bit arithmetic.

For +ve, msb is 0. For -ve, msb is 1.

max(a, b)
- returns a, when a > b, a-b is +ve, so a * 1 + b * 0
- returns b, when b > a, a-b is -ve, so a * 0 + b * 1
// 0 for +ve. 1 for -ve
msb(x):
    return (x >> 31) & 1

// bit is 0 or 1 only
toggle(bit):
    return bit ^ 1
max(a, b):
    return
        a * toggle(msb(a-b)) +
        b * msb(a-b)
But (a-b) could cause overflow when a, b are of different signs.
(int.max, -1), int.max-(-1) = -ve number
(int.min, 1), int.min-1 = +ve number

When a, b are of different signs, the +ve number is max.

So two functions - different signs and same signs.
// when a, b have different signs
f_different =
a * toggle(msb(a)) +
b * toggle(msb(b))

// when a, b have same signs
f_same =
a * toggle(msb(a-b)) +
b * msb(a-b)
So for max, multiply functions with their masks and sum.
a b  a^b
--same--
0 0    0
1 1    0
--diff--
0 1    1
1 0    1

max =
f_different * mask_different +
f_same * toggle(mask_different)

mask_different = msb(a) ^ msb(b)
[Hat tip to ctci]

Saturday, August 08, 2015

2048 game's slide

Get the first two +ve numbers as i1, i2 and keep a target index. If values at i1 and i2 are same, then 2x and loop again from i2-1. Else copy i1 and loop again from i2.
//example

    i2 i1
 -  2  2  -
          target

slide direction -->

i: 0123
a: ..22 = ...4
a: 2.2. = ...4
a: 221. = ..41
a: 2222 = ..44
a: 2.4. = ..24
//time O(n), space O(1)
slide(a):
    target = a.length-1
    i1 = i2 = a.length-1
    while true:
        while i1 >= 0 && a[i1] == 0:
            i1--
        if i1 < 0:
            break
        i2 = i1 -1
        while i2 >= 0 && a[i2] == 0:
            i2--
        t = a[i1]
        if i2 >= 0 && a[i1] == a[i2]: //i1 is >= 0 
            a[i1] = a[i2] = 0
            a[target--] = t << 1
            i1 = i2 -1
        else:
            a[i1] = 0
            a[target--] = t
            i1 = i2