Challenge – Camel and Bananas

Posted on by
3

A few days back I saw this programming question pop up on reddit and I thought it was interesting because I like doing dynamic programming (DP) type problems. Here’s the question,

The owner of a banana plantation has a camel. He wants to transport his 3000 bananas to the market, which is located after the desert. The distance between his banana plantation and the market is about 1000 kilometer. So he decided to take his camel to carry the bananas. The camel can carry at the maximum of 1000 bananas at a time, and it eats one banana for every kilometer it travels.

What is the largest number of bananas that can be delivered to the market?

Initially the number of trips that can be made back and forth between two points kind of threw me off because I wasn’t able to map the problem to a standard DP approach, but once I worked out a formula for the cost of making a trip between two points then I was able to simplify the problem. Next I stumbled down a blind alley where I was trying to model the problem as a two-dimensional DP problem, after mulling over the problem in my free time I finally got the recursive definition down today morning and was able to get the right answer. I think :)

Here’s the formula I used to calculate the bananas left after travelling a given distance,

def bananas_left(start_count, distance):
number_of_trips = (start_count//max_load)
return max(0, number_of_trips * max_load - (2*number_of_trips - 1) * distance * banana_per_mile)

Here’s the DP model I used,

Let M[n] be the max number of bananas at mile n then
M[n] = max { bananas_left(M[k], n-k) } for k = 0 .. n-1

it resembles the coin change DP problem.

Here’s the whole program,

def camel_and_bananas():
total_distance = 1000
banana_per_mile = 1
max_load = 1000
start_load = 3000

def bananas_left(start_count, distance):
number_of_trips = (start_count//max_load)
return max(0, number_of_trips * max_load - (2*number_of_trips - 1) * distance * banana_per_mile)

def print_path(index):
if index > 0:
print("{} bananas at mile {} starting with {} bananas at mile {}".format(M[index], index, M[index - W[index]], index - W[index]))
print_path(index - W[index])

M = [0] * (total_distance + 1)
W = [0] * (total_distance + 1)
M[0] = start_load

for n in range(1, total_distance + 1):
for k in range(n):
if bananas_left(M[k], n-k) > M[n]:
M[n] = bananas_left(M[k], n-k)
W[n] = n-k

print_path(total_distance)

It outputs

533 bananas at mile 1000 starting with 1001 bananas at mile 533
1001 bananas at mile 533 starting with 2000 bananas at mile 200
2000 bananas at mile 200 starting with 3000 bananas at mile 0

Which seems correct.

Calling a web service from SQL Server

Posted on by
Reply

Recently I had to call a web service from SQL Server for integrating with a phone system that only allowed interaction with third-party systems via a database. It seemed straightforward enough given that we can write CLR functions in SQL Server. It ended up taking me a few hours to get all the settings correct before I could make it work.

I started off with this excellent article by bennie which saved me at least a couple of days of work

http://footheory.com/blogs/bennie/archive/2006/12/07/invoking-a-web-service-from-a-sqlclr-stored-procedure.aspx It’s a little old but most of the steps were still the same.

Here are some of the things I ran into that would be useful for anyone doing the same,

1.       If you are using Visual Studio 2010, you do not need to do the post-build event for sgen.exe, instead in the build properties for the project set the “Generate serialization assemblies” to “On”

2.       After you run the alter on the database to set the TRUSTWORTHY option to on, you may get an error message The database owner SID recorded in the master database differs from the database owner SID recorded in database ‘XXXXX’. You should correct this situation by resetting the owner of database ‘XXXXX’ using the ALTER AUTHORIZATION statement.  If this happens you just need to do as the instruction says and run the alter authorization statement to set the db owner to be a login on your server that you trust.

3.       In the manual deployment script, you need remember that the path given for the file of the assembly is a path on the database server and not on your local machine, so you may want to setup a post-build script to either copy the files to the server or use UNC paths and then set the path appropriately in your deployment file.

4.       If you get an exception when running the proc that “There was an error generating the XML document. —> System.Security.SecurityException: That assembly does not allow partially trusted callers.”. Then you need to set the AllowPartiallyTrustedCallers assembly attribute in your assemblyInfo.cs file and deploy the assembly.

Posted via email from Sijin Joseph

Spoon Application Virtualization Technology

Posted on by
2

Spoon uses proprietary app virtualization technology to allow streamed apps to execute instantly in an isolated environment on any Windows desktop. Unlike hardware virtualization solutions such as VMware and Virtual PC, which emulate the underlying hardware and therefore require an entire copy of the host operating system, Spoon app virtualization technology emulates operating system features required for execution.  As a result, Spoon virtual apps have essentially the same performance characteristics as native executables.

The core of Spoon app virtualization technology is the Spoon virtual machine (VM) kernel. The Spoon kernel is a lightweight implementation of core operating system APIs, including the filesystem, registry, process, and threading subsystems, completely implemented within the user-mode space, allowing Spoon apps to be executed without any device driver installation or administrative privileges.

Apps executing within the Spoon virtual environment interact with a virtualized filesystem, registry, and process environment, rather than directly with the host device operating system. The virtualization engine handles requests within the virtualized environment internally or, when appropriate, routes requests to the host device filesystem and registry, possibly redirecting or overriding requests as determined by the app configuration:

 

via spoon.net

This is a cool technology, instead of virtualizing the entire computer hardware, this allows virtualizing only the parts needed by individual applications, that combined with a streaming technology allow you to run for e.g. multiple browser versions in the cloud.

[Update] This is actually cooler than I thought, I ran FF 4 beta using spoon and realized that the browser is actually running on my machine and not on the cloud, because when I goto open or save files, it shows the location as being my computer. Awesome!

Posted via email from Sijin Joseph

Youthful Arrogance

Posted on by
5

In 2000 when I had just started my master’s degree I had already been programming in C/C++ and VB for some years prior, mostly simple LoB apps for my dad’s business and some other telecom programs that I had written while working as an intern during my undergrad years studying mathematics. I thought of myself as being above the rest of the class in terms of programming skills and knowledge of how software worked and was written. Funnily enough I even thought of myself as being better than my professors, who I thought were just stuck in academia and didn’t know how real programming was done. Now 10 years later after being a professional programmer for 8 years I feel disappointed by my attitude towards my professors and regret not having made better use of my time doing academic work rather than focusing on more practical programming tasks.

Here are some of the incidents that I recollect,

Freshman year, my professor for "Programming Languages" was teaching about how different languages implement, static vs dynamic, lexical scoping, setup of call frames, how call frames are linked to the global environment etc. At this point the only language I knew well was VB and was comfortable coding in C++ and Java. Based on my miniscule knowledge of these imperative languages I started questioning all that she was teaching in a very negative tone, my prof did answer all my questions correctly but since I didn’t know anything beyond what I knew I couldn’t believe she was teaching all this bullshit to us. I don’t quite remember what I was arguing about (closures maybe?) but since the rest of my class were even more clueless than me they thought I was cool to stand up to the prof and question her the way I did. Now after all these years and having read and used a much larger set of languages I feel stupid for thinking that my prof didn’t know what she was saying. FAIL!

Freshman year, my professor for data structures and algorithms was teaching us some introductory C, he showed us the canonical C expression for copying strings *dest++ = *src++; When I saw this on the board, I started shaking my head and telling my classmates that the prof was teaching incorrect code. So right after the class I went up to him and told him that I felt that the code he had written was wrong and that it would not work, he looked at me, smiled and said "You’ve just seen this today, take some time to absorb it and let me know if you still think it is wrong". I thought he was just avoiding me and never really bothered to look it up. Years later when I first read K&R C (One of the best books on C IMO) I was enlightened. How arrogant of me to think that this professor from Stanford University didn’t know how to write C code, I suck.

Another incident with the same professor that I remember is when we were asked to write a solution for the 8 queens problem, rather than focus on writing a good algorithm I wanted to showcase my programming skills and wrote a program that given any set of chess-pieces would tell you if there was a way to place them on the board so that they didn’t threaten each other, the code was probably 10 times longer than a solution to the simple 8-queens problem and when I saw the solution that my prof. presented using arrays and 3-4 lines of backtracking code, I thought that my code was definitely better. Now that I look back, I realize that the focus was more on the algorithm and that the efficiencies achieved by the code written by my prof would have blown my code out of the water. This prof had taught at Stanford University, If I had the chance to go back, I’d definitely get on his good side and maybe get a recommendation to study at Stanford. What a wasted opportunity!

Sophomore year I had a course in Artificial Intelligence, for some reason I don’t think I ever attended enough classes for that course and did any of the coursework, if only I had known that doing anything with AI the rest of my professional life would be a pipe dream, I’d have soaked up AI and actually written some AI programs that year, maybe learnt LISP/Scheme, read Paradigms of Artificial Intelligence, learnt statistical methods for expert systems, instead of goofing around and trying to study the night before just to pass the exam. :(

Another professor in sophomore year was a visiting professor who a retired army man, he wanted to teach us this new language called Python. He said that he’s used a lot of languages and Python was going to rule them all, another thing he wanted us to learn was SIP because he thought that SIP was the future. Silly me and my naive belief in C++ being the greatest language ever, I used to hang out at codeproject.com a lot back then and I posted something about how idiotic this professor was trying to teach us a "typeless" bastard language…ROTFL…how much more arrogant could I get…looking back now at the widespread use of Python and SIP I only wish I had stayed in touch with the professor and made better contacts with him and actually gotten into Python and SIP way back then. I’d actually have some pretty cool stuff on my resume instead of the usual run of the mill app programming experience.

In my senior year, we were supposed to submit a thesis. Most of the other professors allowed you to do an internship at a software company and use the work there as your thesis instead of actually doing research and submitting a thesis. I just assumed that my professor would be the same and spent the whole semester working at an outside software company, when I met my professor for the first time was on the day we were supposed to submit the thesis. He was shocked that I wanted him to sign on something he was seeing for the first time. So he had me come back the next day, looked at what I had done and tried to morph that into a thesis on text mining. He had me read up papers, look up research journals online and basically write a proper thesis instead of a project report which I had submitted earlier. During my interactions with this professor I realized how academically good he was in terms of his connections with other professors around the world, the papers that he had published and the research that he was doing at the university. Looking back now, I wish so much that I had gone to him right when the year started and spent the year actually doing research and writing a thesis instead of writing software.

I know hindsight is 20/20 but it just seems like I could have made a lot better use of my time during those years instead of spending my professional years wanting time to do the same.

Posted via email from Sijin Joseph

Ubuntu Install Experience

Posted on by
1

Last week I decided to install Ubuntu 10.10 on my wife’s 4 year old laptop as a primary operating system. My last experience installing Linux as the primary operating system was from the early Red Hat days, since then I had always installed Linux as a virtual machine using either Virtual PC or more recently VirtualBox.

I had to use UNetBootin to install from USB because the DVD drive on the laptop would not read certain parts of the install disk, but once it got started with the USB boot and subsequent install, things went pretty smoothly and I was up and running with a fully updated installation in 20 minutes.

I was amazed at how much the whole install experience for Linux has improved with Ubuntu. First of all, even before the installation started it had detected my wireless card and had me connected so that any updates could be downloaded and installed while the setup was running. And after the install, every piece of hardware on this old laptop worked, no driver issues or anything.

The only pieces of software she needed were Chrome and Skype, and the synpatics package manager made installing those a breeze, so I had this new laptop setup and ready to go in 30 minutes. What a world of difference. And now with the browser being the primary means for our family to access most of our apps and data it doesn’t really matter that the amount of software available for Linux doesn’t match the quantity available for Windows or OS X, Ubuntu is good enough for us.

Posted via email from Sijin Joseph

Oracle to start charging for MySQL – Standard edition @ 2000 USD

Posted on by
2

MySQL Editions

MySQL is the world’s most popular open source database. Whether you are a fast growing web property, technology ISV or large enterprise, MySQL can cost-effectively help you deliver high performance, scalable database applications.

MySQL is available in multiple editions to meet your business and technical requirements:

  MySQL Classic Edition MySQL Standard Edition MySQL Enterprise Edition MySQL Cluster Carrier Grade Edition
Annual Subscription2,3,4,5,6
/1-4 Socket Server /Year		 N/A USD 2,000 USD 5,000 USD 10,000
Features
MySQL Database ? ? ? ?
MySQL Connectors ? ? ? ?
MySQL Replication ? ? ? ?
MySQL Partitioning     ? ?
MySQL Workbench SE1   ? ? ?
Storage Engine: MyISAM ? ? ? ?
Storage Engine: InnoDB   ? ? ?
Storage Engine: NDB       ?
MySQL Enterprise Monitor1     ? ?
MySQL Enterprise Backup1     ? ?
MySQL Cluster Manager1       ?
MySQL Cluster Geo-Replication       ?
via mysql.com

Oracle has started charging a fees for most editions of the once free and open source MySQL server. Wonder what effect it’ll have on startups that chose MySQL just because of the cost advantage.

Posted via email from Sijin Joseph

The 5.2 billion dollar mistake. « Steve Blank

Posted on by
Reply

When Iridium was first conceived inside Motorola in 1987, worldwide cell phone coverage was sparse, calls were unreliable and per minute costs were expensive. Cell phone handsets were the size of a lunch box and cost thousand of dollars.

Motorola Dynatac 8000x ~1987

When it was spun out as a a separate company, Iridium’s 1990 business plan had assumptions about potential customers, their problems and the product needed to solve that problem. All were predicated on the state of the mobile phone industry in 1990. They made other assumptions about the type of sales channel, partnerships and revenue model they would need. And they rolled all of this up into a set of financial forecasts with a “size of market” forecast from brand name management consulting firms that said they’d have 42 million customers by 2002. Iridium looked like it would be printing money when it got its satellites into space.

A Business Plan Frozen in Time
But in the 11 years it took Iridium to go from concept to launch, innovation in mobile phones and cell phone networks moved at blinding speed. By the time Iridium launched, there were far fewer places on the planet where cell phone service was unavailable. Traditional cell phone companies now had coverage in the most valuable parts of the world. Prices for local and international cell service declined dramatically. The size of a cell phone handset had shrunk so it could fit in your pocket.

In contrast, when Iridium’s service became available its satellite phone was bigger than a brick and weighed about the same.

iridium-9500 satellite phone ~1999

Worse, Iridium’s cell phone couldn’t make calls from cars, offices or other buildings since phones had to be used outdoors with a line-of-sight connection to the satellites. But the nail in the coffin was price. Instead of the 50 cents per minute for a regular cell phone, Iridium’s calls cost $7 per minute– plus users needed to pay $3,000 for the handset.

In the eleven years since they had been at work, Iridium’s potential market had shrunk nearly every day. But Iridium’s business model assumptions were fixed like it was still 1990. They were dead on arrival as a mass market cell phone service the day they went live.

via steveblank.com

I always wondered what had happened to Iridium. When I was in high school I thought this company was going to take over the world. I still remember being impressed with their advertisements about being able to take calls from the middle of Sahara desert. :)

Posted via email from Sijin Joseph

Microsoft shifting to HTML5 as primary cross-platform runtime

Posted on by
1

But when it comes to touting Silverlight as Microsoft’s vehicle for delivering a cross-platform runtime, “our strategy has shifted,” Muglia told me.

Silverlight will continue to be a cross-platform solution, working on a variety of operating system/browser platforms, going forward, he said. “But HTML is the only true cross platform solution for everything, including (Apple’s) iOS platform,” Muglia said.

via zdnet.com

Wow, looks like Microsoft if taking some radical steps to get back into the game. I think this is the right direction to go for Microsoft.

Posted via email from Sijin Joseph

SPTH ‘Taking the redpill: Artificial Evolution in native x86 systems’ (VX heavens)

Posted on by
Reply

1.1.1. CoreWorld

Arti?cial evolution for self-replicating computer codes has been introduced for the ?rst time in 1990, when Steen Rasmussen created CoreWorld.[1] CoreWorld is a virtual machine which can be controlled by a language called RedCode. This assembler-like language has a pool of ten di?erent instructions that take two addresses as arguments. Rasmussen’s idea was to introduce a random ?aw of the MOV command, resulting of random mutations of the self-replicating codes within the environment. The big disadvantage of RedCode was, that nearly all ?aws led to a lethal mutation, hence evolution did not occure as wished.

1.1.2. Tierra

In 1992, Tom Ray found out that the problem with RedCode was due to argumented instruction set: Independent mutations in the instruction and its arguments are unlikely to lead to a meaningful combination.[2] Instead of direct connection between the instruction and its argument, Ray developed a pattern-based addressing mechanism: He introduced two NOP-instructions (NOP0 and NOP1). These instructions do not operate themselve, but can be used as marker within the code. A pattern-matching algorithmus would ?nd the ?rst appearence of a complementary marker string given (after the search-command), and returns its addresse.

PUSH        AX        ; push ax JMP NOP0 NOP1 NOP0                ; jmp marker101 INC        A        ; inc ax NOP1 NOP0 NOP1                ; marker101: POP        CX        ; pop cx  

There are 32 instructions available in the virtual Tierra world, roughly based on assembler (JMP, PUSH AX, INC B and so on). With these inventions, Ray was able to gain great results for arti?cial evolution (like parasitism, multi-cellularity[3][4], …).

1.1.3. Avida

In 1994, Christoph Adami has developed another arti?cial evolution simulation, called Avida. Beside of some di?erent structures of the simulation, an important change has been made in the arti?cial chemistry: Instead of hardcoded arguments within the instructions (as in Tierra for example PUSH AX), instructions and arguments are completely separated. The arguments are de?ned by NOPs (in avida there are three NOPs: nop-A, nop-B, nop-C) following the operation (for example, a nop-A following a PUSH pushes the AX-register to the stack). There are 24 instructions available in avida, again roughtly based on assembler (call, return, add, sub, allocate and so on).

push nop-A                ; push ax jump-f nop-A nop-B nop-B                ; jmp markerBCC inc nop-A                ; inc ax nop-B nop-C nop-C                ; markerBCC: pop nop-B                ; pop bx  

With that improvements of the virtual simulation, the researchers using avida found out amazing results, among other things about the origin of complex features in organism [5].

via vx.netlux.org

Very interesting paper on creating a evolutionary system for native x86 systems. This is an area that has fascinated me since I first studied genetic algorithms. However I didn’t realize that this was being done for native x86 instruction sets as well, I always assumed that the environment was a virtual one.

Posted via email from Sijin Joseph