…due to my unexpected Ubuntu trial at work.

• It’s bloody good. Looks lovely. I’d quite happily use this full time if I had that choice/option (not like there’s any competition with XP, but I mean I’d also switch from OSX for this; Was never a fan of the brown theme, preferring Mint, but I prefer this new theme to Mint).
• Does multiple monitor support pretty much no problem. (The first time I set them up, laptop (1440x900) and monitor (1280x1024), I had a few glitches getting the settings to work: I had to apply the settings a few times and toggle between settings, etc until it worked ok. But subsequent times it worked first go. Bizarre.)
• You can move the menus bars to the ‘main’ monitor.
• To get Lastpass working, had to launch from terminal and be sure to export HTTPS_PROXY before hand
• Non-persistant LiveUSBs aren’t that bad afterall: I used to use Slax a fair bit, because it’s small, looks good and I could have a persistant install on a 1GB usb stick (I don’t have the min 2gb for a persitant Ubuntu install :-( ). But then I twigged, there’s not that much downside to a LiveUSB install in cloud-computing land: I’ve just moved my Firefox profile onto another USB stick and I can reconnect to that each time I used the LiveUSB; tweaking other settings each time isn’t so bad.
• Be VERY careful when installing to an external USB drive from the LiveUSB. The default settings will happily trounce the MBR of the internal drive. And although in theory this is fixable, in mine it wasn’t. Whole laptop had to be re-imaged. Ooops.

• Tags:
  • code

Comments

Or subtitled: Why turn down a chance to completely embarrass myself on the internet?

I read this post on Binary search on the Reinvigorated Programmer blog (In trying to learn more programming, I thought it wouldn’t hurt to read some programming blogs; plus as an unexpected bonus he likes Doctor Who) and thought I’d have a crack at it. However, the rules were a bit hard for me, namely:

“NO TESTING until after you’ve decided your program is correct.”

Even with Ruby, which I’m vaguely familiar with, I knew I couldn’t possibly write even the most basic program without resorting to trying out stuff in IRB. It’s the same as simple maths (times tables, etc) and spelling for me - I make no attempt to memorise this stuff when it’s easy to use a calculator, dictionary, etc. So that’s how my programming works. I can write a vague outline of the logic required in note form, but I need to use IRB or (if in another language) break my programme into chunks to compile and test, etc.

So, an honest a first attempt as possible (with just checking things like “How do ranges work in arrays again?” in IRB (told you it was embarrassing)) would be as follows:

First Attempt

#Assumes a pre-sorted array
def binsearch(array, target)
    m = (array.length/2).floor #round down 
    until array[m] == target
        #Find middle value of array
        m = (array.length/2).floor #round down 
        puts m
        #Which half contains target
        if array[m] > target
            #delete top half
            array = array[0..m]
        else 
            #delete bottom half
            array = array[m..-1]
        end
    end
    puts m
    puts target
    #Do we need to know where we found it?
end

This doesn’t work, the main problem being that I didn’t understand/forgot/didn’t-think-about-it-properly how the loop would check its condition. With m being updated at the start of the loop, it’s too late - the loop has begun so it’ll carry on and never break out of a loop.

Oh well, a bad first guess. At least with that out of the way I could try again, but this time I could test as I went along.

Second Attempt

  def binsearch(array, target)
   #Find middle index of array
    m = (array.length/2).floor #round down
    until array[m] == target
        puts m
        #Which half contains target
        if array[m] > target
            #delete top half
            array = array[0..m]
        else 
            #delete bottom half
            array = array[m..-1]
        end
       m = (array.length/2).floor #round down 
    end
   puts "Value found is " + array[m].to_s
   puts "Target was " + target.to_s
    #Do we need to know where we found it?
 end

The main change is moving the update of m from top of loop to end. This got it basically working. I then decided (and I don’t think this is a requirement of the task set) to report out the index of the array where the result was found (because to me there didn’t seem to be a lot of point searching for something without knowing where it is).

Third attempt

 def binsearch(array, target)
    #Duplicate array so we have a copy of the original
    orig = array.dup

    #Find middle index of array
    m = (array.length/2).floor #round down
    #tracking index
    tidx = m
    until array[m] == target
        puts "m= " + m.to_s
        puts "tidx= " + tidx.to_s
        #Which half contains target
        if array[m] > target
            #delete top half
            array = array[0..m]
            subtractidx = true
        else 
            #delete bottom half
            array = array[m+1..-1]
            subtractidx = false
        end
        m = (array.length/2).floor 
        if subtractidx == true
            tidx = tidx - m + 1
        else
            tidx = tidx + m + 1
        end
    end
    puts "Value found is " + array[m].to_s
    puts "Target was " + target.to_s
    puts "Index of value is " + tidx.to_s
    puts "Value at index is " + orig[tidx].to_s
 end

I’d mucked up splitting the arrays and had overlapping ranges, 0..m and m..-1 so fixed that here as well. This attempt seemed to be working ok, but having accidentally seen a bit of the next post that dealt with common bugs in other people’s attempts at this problem, I knew there were things I’d not done: such as dealing with elements not in the array, etc. So that would be the next effort. Fair enough I wouldn’t have got this with my first “paper” attempt anyway, but I would have twigged pretty soon with testing (and as I said, testing is how I develop).

Fourth attempt:

def binsearch(array, target)
    #Duplicate array so we have a copy of the original
    orig = array.dup
    found = true
    #Find middle index of array
    m = (array.length/2).floor #round down
    #tracking index
    tidx = m
    until array[m] == target
        puts "m= " + m.to_s
        puts "tidx= " + tidx.to_s
        #Which half contains target
        if array[m] > target
            #delete top half
            array = array[0..m]
            subtractidx = true
        else 
            #delete bottom half
            array = array[m+1..-1]
            subtractidx = false
        end
        m = (array.length/2).floor 
        if subtractidx == true
            tidx = tidx - m + 1
        else
            tidx = tidx + m + 1
        end
        if array.length == 1 and array[m] != target #if not found
            found = false
            break
        end
    end
    puts found
    if not found
        puts "Value not found"      
    else
        puts "Value found is " + array[m].to_s
        puts "Target was " + target.to_s
        puts "Index of value is " + tidx.to_s
        puts "Value at index is " + orig[tidx].to_s
    end
 end

This still wasn’t completely right though. I.e. the index was not always right.

Fifth attempt

def binsearch(array, target)
    #Duplicate array so we have a copy of the original
    orig = array.dup
    found = true
    #Find middle index of array
    m = (array.length/2)-1
    #tracking index
    tidx = m
    until array[m] == target
        puts array.to_s
        puts "m= " + m.to_s
        puts "tidx= " + tidx.to_s
        #Which half contains target
        if array[m] > target
            #delete top half
            array = array[0..m]
            subtractidx = true
        else 
            #delete bottom half
            array = array[m+1..-1]
            subtractidx = false
        end
        m = (array.length/2)-1 
        if subtractidx == true
            tidx = tidx - m - 1 
        else
            tidx = tidx + m
        end
        if array.length == 1 and array[m] != target #if not found
            found = false
            break
        end
    end
    puts found
    if not found
        puts "Value not found"      
    else
        puts array.to_s
        puts "m= " + m.to_s
        puts "tidx= " + tidx.to_s
        puts "Value found is " + array[m].to_s
        puts "Target was " + target.to_s
        puts "Index of value is " + tidx.to_s
        puts "Value at index is " + orig[tidx].to_s
    end
 end

Trying to get the index correct, but still crap. I did discover though that I didn’t need the floor method to round down, as that was happening anyway (see, further embarrassment). Decided to give up figuring this (index tracking) out. Must be a simpler way. Rather than split the array up, just change the range we are looking at:

Sixth (and final-ish) attempt

def binsearch(array, target)
    #Assume search suceeds
    found = true
    #initial lower, upper and middle indexes
    l = 0
    u = array.length-1
    m = (u-l)/2
    until array[m] == target
        #Visualise the search
        puts array[l..u].to_s
        puts "l= " + l.to_s
        puts "m= " + m.to_s
        puts "u= " + u.to_s
        #Which half contains target?
        if array[m] > target
            u = m #Set new upper boundary
        else 
            l = m + 1 #set new lower boundary
        end
        m = (u-l)/2+l #set new mid point
        #Break if not found / out-of-range
        if l==u and array[m] != target
            found = false
            break
        end
    end
    #Visualise search
    puts array[l..u].to_s
    puts "l= " + l.to_s
    puts "m= " + m.to_s
    puts "u= " + u.to_s
    if not found
        puts "Value not found"      
    else
        puts "Value found is " + array[m].to_s
        puts "Target was " + target.to_s
        puts "Index found at is " + m.to_s      
    end
 end

Ok, so pretty happy with that. Seems to work ok. It’s longer than it needs to be thanks to all the puts statements, but I like seeing how it arrives at the solution. Seems to find values, return correct indexes, deal with values not in the array. But what about single element or zero element arrays (also accidentally peeked at)? Whoops no good.

e.g.

binsearch([0], 1)
binsearch([-1], 1)
binsearch([-1], 0)

all just loop continuously, and

binsearch([], 1) 

throws an error.

Zero length arrays are not such a worry, easy to check for that up front (even for me!), but the single element one going into a continuous loop is a more of a concern. A crappy, but simple fix would be:

if array.length == 1
    if array[0] == target
        #Joy to the world
    else
        #Best stop things now
        break
    end
end

But I’m sure there is a more elegant way?

Finally

I’d like to be able to use a get out clause:

I am confident that nearly everyone who reads this blog is already familiar with the binary search algorithm

and say “Well, nope I’m not familiar”, which I’m not, but I did understand the principle of the search. Really this just harks back to school Maths (which was a while ago for me) and iterative searches, etc. “Binary Search” is just different terminology. So no excuse really - I should have been able to figure it out. Perhaps what I should have done was forget the programming language aspect and just write it down logically/mathematically. Ah well, eager beaver and that.

Guess I have a long way to go yet if I want to be a programmer.

• Tags:
  • code

Comments

Colour as bleeding obvious, but in HTMLUnit I could not figure out how to “just use WebClient.setTimeout(int)”.

I was searching for something like this:

try{
    webClient.setTimeout(60000);
    HtmlPage page = (HtmlPage) webClient.getPage("http://somepage");
}
catch(TimeoutError e) {
    //Try again, or abort, etc
}

Except TimeoutError is made-up. I was sure setTimeout() must cause an exception, otherwise what the hell was the point of it? But no amount of searching would give me the answer, I’d either end up on the trail to “just use WebClient.setTimeout(int)” or finding my exact question, but with no answer at all.

Turns out all I needed to do was to piece together these two bits of information:

1. setTimeout Sets the timeout of the WebConnection.

2. WebConnection - Throws: IOException - if an IO error occurs

Yes, handling timeouts is as simple as

try{
    webClient.setTimeout(60000);
    HtmlPage page = (HtmlPage) webClient.getPage("http://somepage");
}
catch(IOException e) {
    //This catches a timeout error as well
}

(Thankfully I figured this out before I asked on Stackoverflow - because it turns out there is such a thing as a stupid question)

• Tags:
  • code

Comments

I had occasion to get this working again. Not that it’s hard mind you, just that I gave up too easily last time. I’d been logging an xml response from a Java programme and ended up with a massive xml file all on one line. Obviously not ideal if you want to search through the file.

Googling lead to xmllint, and last time I didn’t even try after reading about Windows difficulties.

Turns out it’s simple.

1. Just download xmllint for Windows.
2. Simply place the executable in the same directory as the xml files for the lazy approach
3. :% !xmllint.exe % --format from within vim. (The syntax on the wiki page was wrong (for windows at least), :! xmllint.exe --format % tries to load the file “—format”, need to swop the order of the % and the flag. Also the leading % is required (referring to the currently open file) as otherwise it’ll run it through xmllint, but will not actually replace the contents of the file you have open.)
4. Done

But then I read another wiki page and found this much more clever approach:

:%s/></>\r</g
:0
=:$

The % means search the whole file, performing a search and replace using this syntax: s/search/replace/g. So it’s searching for “><” and replacing with the same, but with the addition of \r which simply means split line at this point. Dead clever. Requiring nothing more than vim itself. The rest (:0 and =:$) is just moving back to the start of the file and indenting it all.

(I’ve been a good boy and edited the wiki)

• Tags:
  • code

Comments