I’d be leaving Budapest after Christmas. I hear Budapest is even more beautiful during the Christmas season. That’s plausible. So I’d stay in Budapest until the last day of this year. Today I spent some time thinking about how much stuff I can take out of Budapest. Apparently, Lufthansa allows me to check in only one bag and carry on one bag. Ridiculous, right?

But anyways I need to figure what I can put into the bag to check in and what I’ll have to mail somehow to the States. I have a list of things I’ve bought so far and things I wish to buy + how much these things weigh. The tricky thing is that there’s no clear positive or negative correlation between things that I want (or prefer) to take and the weight of these things. For example, I have a cup that I like that weighs 1kg, a 0.8kg World War 2 Galilean binoculars I bought today that’s kind of expensive and that I really like, and another WW 2 artifact, a butterfly knife that weighs 0.5kg. I don’t really like the butterfly knife but I think it’s better if I put it in the checked bag rather than mail it. I feel U.S customs might delay its entry if I mail it.

So my dilemma is to try to fit all the articles I’ve bought, the ones that I plan to buy, and the ones that I already have into a 23kg bag. Let’s assume that the
weight of all the items I came with (altogether) is about 20kg. The remaining space available is obviously 3kg. Here’s a list of the potential articles:

To make it easier for me to know which items I should take and which I shouldn’t,
I associated each item with a preference number. The more I like an item, the higher
it’s preference number.

Another way of stating this problem is: I have a max space (3kg). I need to
fill that space with items from the above list. But in selecting the items, I wish
to maximize the total Preference of the selected items.

This problem is pretty easy to solve and there are many known heuristics and
algorithms you can use to solve this problem. Check out the solution here.

The problem is very similar to the Levenshtein distance problem so I won’t write out the full solution code but will direct you to resources online.

The Levenshtein distance is an edit distance metric. An Edit distance metric is used to determine how similar a source word is to a target word. The allowed operations to transform a source word to a target word are insertion, deletion, and substitution. An aside: there’s another edit distance metric called the Damerau–Levenshtein distance. I advise that you check this one out. It adds another operation to the suite of available operations on the source word: the transposition of adjacent characters.

Let correspond to the source and the target word respectively. The person who knows how to speak English the best (according to me – might be a slack metric but it works) is the person who scored .

The recurrence relation is defined on the wikipedia page for the Levenshtein distance. Plus, there’s also some pseudocode that should guide you on how to solve the puzzle.

Some more hints:

•  Remember that the cost for insertion and deletion should be the same (maybe, 1).
• The cost of substitution should be strictly less than the cost of deletion or insertion (maybe, 0.5).

Y’all can take it from here!

Hey, this is the first problem in a series of programming problems/puzzles I’ll be posting during my study abraod in Budapest, Hungary. If you like this puzzle and its solution, come back for more. If you don’t, tell me how I could improve the puzzle and/or  solutions format via comments on this blog.

Before arriving Budapest, I tried to learn basic hungarian phrases used in day-to-day discussions. I learned to introduced myself: Jo napot, a nevem Daniel. I also learned to ask to use the toilet, ask for directions, and let my interlocutor know that I don’t speak Hungarian. But how much Hungarian have I used in my conversations thus far? None. Most young people in Budapest speak acceptable english. I’d rather speak in a language with which I’m very familiar with than converse in a very beautiful language that I have a strenuous grasp on. The puzzle below is a fictional attempt to sift out the young people who speak english very well.

Puzzle 1: Anyone Speak English Here?

I currently live around Astoria in Budapest. I want to go to the mall to purchase a video camera to use during the Hungarian drinking festival in the Buda Castle in the Buda side of Budapest. I have to use the subway. But I don’t know which metro line I should use. I’m determined to figure it out by asking someone, in English, around the metro station area to tell me when to get on and when to get out of the metro line when I arrive the Castle. To do that, I must first sift out the young people who speak English by using some algorithm (maybe?).

I’ll give my target young person an English word and ask him/her to give me another English word that’s closest to it. The distance metric I use to measure closesness of words uses costs on substitution, insertion, and deletion of characters in the word given. I prefer that fewer characters be deleted from or inserted into the source word. Substituting one character for another is, therefore, preferred over insertions or deletions of characters.

Example:
Source word: rain
Target words: pain, raining, in
pain is the preferred word here since the character ‘p’ is substituted for ‘r’ and no insertions or deletions take place. The other words (in, raining) are gotten through a rain of deletions and insertions (me don’t like this!).

Now, you’ve gotten my gist (or my dilemma), try to come up with an algorithm that’ll accept as input a source word and a list of target words and output what word I prefer the most. By knowing what target word is “closest” to the source word given, I can determine which youth speaks the better English and finally find my way to the mall!

The solution to the problem is here. But before you go there try to solve it on your own. A hint – this problem is very similar to another distance metric problem.