Featured

IDL for Rapid Scripting of Image Processing

Interactive Data Language (IDL) is a language environment for rapidly scripting algorithms for processing imagery. IDL is closely tied to the more graphical ENvironment for Visualizing Images (ENVI) image processing environment from the same company. This simple high-level scripting language, supported by extensive tools, enables quickly hacking algorithms to find workable solutions.

IDLlogo

IDL enables rapidly roughing out ideas at a high level by freeing developers from first building an extensive tool-kit of common image processing routines. As with most scripting languages, there is no need to declare variables with specific data types as in lower-level languages like C/C++. This level of control is available for optimizing performance on large arrays of data.

IDL is interactive, allowing the developer to enter and execute code fragments line by line without compiling and linking. Once the code fragment matures to being useful, it is simple to edit into a text file that can be run as a function or program within the IDL environment. Although the IDL library of functions is extensive, there will always be more functions that you will want to add.

As functions in IDL mature, they can be ported to lower level languages and compiled into binary executable code or libraries to improve speed and reduce memory requirements.

You can continue running algorithms in IDL as long as you have a licensed copy. But applying your algorithms more broadly on machines that do not have IDL, will require porting to another language.

Although there is an open-source version of MatLab, Octave, I have not heard of an open-source version of IDL. IDL does have a virtual machine that enables running IDL code “compiled” on a fully licensed version.

Dropping Two Eggs Puzzle

You are given 2 identical eggs and a 100-floor building.

An egg dropped from the Nth floor or above will break.

But, it will not break if dropped from any floor below N.

How do you find N with the fewest number of drops for the worst case?

How high before they break?
How high before they break?

Solution:

Drop the first egg from floors K1, K2, … Kz until it breaks on drop z.

Then drop the second egg from floor K[z-1]+1 and each floor above till it breaks when dropped from floor N.

Finding N takes z + N – K[z-1] drops.

If the first egg breaks on the second drop, it will take the same number of drops to find N if K1 = K2 + 1.

Generalize to K[i+1]=K[i]-1.

Starting at K1=14 would reach the 99th floor as the 11th drop of the first.

Worst case is 14 drops for N=14,27,39,50,60,69,77,84,90,95, and 99.

Magic Hats Puzzle

Five people are stranded on an island.

A wizard comes and places a magic hat on some of their heads.

At least one of them now has such a hat.

Each hat can be seen by everyone but the wearer.

To remove the hat, those (and only those who have a hat) must dunk themselves underwater at exactly midnight.

The people cannot communicate until after the hats are removed.

They all want to remove the magic hats as soon as possible.

How long does it take the people to remove the hats?

How long to remove?
How long to remove?

 

Solution:

It will take N days to remove N hats.

On the first day, anyone seeing a hat will not know if they have one too.

Anyone seeing no hat on any head will know it must be on his head and remove on the first night.

On the second day, only the two with hats will see one hat on the rest, and they will know to remove them at midnight.

On the N’th day, N people will see N-1 hats and know they have a hat.

Remove N hats in N days.
Remove N hats in N days.

Dominos on a Chess Board

Given a standard 8×8 chessboard, but 2 diagonal corners are removed.

We seek to cover the squares with dominos.

Each domino covers exactly two squares on the chess board.

You are not allowed to cover the same square twice.

Can you cover the remaining 62 squares with 31 dominos?

Can dominos cover a chess board with 2 missing squares?
Dominos cover a chess board missing 2 squares?

 

Solution:

No, each domino must cover a white and a black square.

The number of white and black squares are not equal after removing 2 diagonal corners.

ChessDominoSol
Reduce to 2×2, 3×3, or 4×4 board.

Lockers Puzzle

You are given a row of 100 lockers, initially all closed.

On the first pass, every locker is opened.

On the second pass, every second locker is closed.

On the third pass, the state of every third locker is toggled from open to closed or closed to open.

If this continues for 100 passes, how many lockers are open?

How many closed?
How many closed?

 

Solution:

Note that after the k’th pass, the first k lockers stop changing.

Before taking on the challenge of 100 lockers, let’s look at the first 12 lockers after the 12’th pass.

They are closed except for 1,4, and 9.

On pass k, locker numbers that are a multiple of k are toggled.

A locker number with an even number of integer multiples is toggled open then closed.

For a locker to remain open, it must have an odd number of integer multiples.

This occurs for numbers that are the squares of integers.

For 100 lockers, there are 10 numbers that are squared integers: 1,4,9,16,25,36,49,64,81, and 100.

For k lockers, floor(sqrt(k)) will be open.

The final state
The final state

Sorting Resistors Puzzle

An engineer ordered 9 boxes of 100-ohm resistors and a box of 110-ohm resistors.

All 10 boxes arrived with 10 resistors each,

but both the boxes and the resistors were unmarked.

The engineer needs to find which box has the 110-ohm resistors.

He has an ohm meter to measure resistance.

How can he find the 110 box with the fewest resistance measurements?

Which box has 110 ohms?
Which box has 110 ohms?

 

Solution:

Label the boxes, “1”, “2”, …, “10.”

Connect in series, 1 from 1st box, 2 from 2nd, and so on till 10 from 10th box.

Measure the resistance (M) of this series of 55 resistors.

If all 55 were 100 ohms, then M = 100*(1+2+…+10)=5500.

We find the box of 110-ohm resisters from this one measurement as

Box = (M-5500)/10.

The measured resistance R will only be 10 ohms larger that 5500 if the first box contains 110-ohm resistors.

One measure of 55 resistors.
One measure of 55 resistors.

Counterfit Coins Puzzle

A king collects 10 gold coins as a tax from each of 10 provinces.

Each coin weighs 10 grams.

The king learned that one province is shaving off 1 gram from each of their coins.

The king examines the coins with a balance scale.

The scale has 2 trays, we label them “A” and “B”.

The scale can provide 3 results, “A<B”, “A>B”, and “A=B”.

How can the king minimize the number of uses of the scale to find which province is cheating?

How can we find the light coins in the fewest measurements?
How can we find the light coins in the fewest measurements?

 

Solution:

Take 1 coin from each province and mark / label where it came from.

At each stage, we seek to separate the coins into 3 equal sets.

We only use the scale to compare sets of coins with equal number.

If the scale results is “A=B”, then all of the coins in A and B are true.

Divide the 10 coins into 3 groups, of 3, 3, and 4.

Weighing 1: Compare 2 sets of 3.

If one of the sets of 3 is lighter, the problem reduces to that set of 3.

Weighing 2: Compare first coin with second coin from the set of 3.

If result is “A=B” then the third is light coin, otherwise the lighter.

If comparing the sets of 3 results in “A=B”, then examine the set of 4.

We divide the set of 4 into sets of 1,1,and 2.

Weighing 2: Compare first set of 1 with second set of 1.

If one of the sets of 1 is light we have the answer, otherwise

Weighing 3: Compare final 2 coins.

There is 80% probability that we will only use the scale twice.

Expected number of uses of scale = 2.2.

Post Office Puzzle

The mail system in Fictionstien is notoriously corrupt.

Anything easily opened, will be, and everything inside taken.

But the postal workers never bother with anything locked.

Boris in Capital City bought a gem to give to Natasha, in Small Town, but neither could travel.

He had a box with a hasp multiple padlocks could be attached to.

Sending the gem locked in the box through the post would be safe.

But she could not open it without the key.

If he send the key separately it would be opened, and removed.

Boris and Natasha hatched a clever scheme to get the jewel to her safely.

What was their scheme?

How did the gem get through the mail safely?
How did the gem get through the mail safely?

 

Solution:

Boris locks the gem in the box and mails to Natasha.

She puts her lock on the box and mails it back to him.

He takes off his lock, and returns it to her with only her lock.

She opens the box as soon as she gets it.

This is safe, but takes 3 trips through the mail, so slow.

Alternative Solution: Cut the Gordian knot.

Boris locks the gem in the box and mails to Natasha.

She decides not to wait and destroys the lock and opens the box.

Three Lights Puzzle

An electrician finds 3 switches that control 3 lights in a distant room.

He cannot see the lights from the room with the switches.

He needs to figure out which switch controls which light.

You can assume each switch controls only one light, and that each light/switch pair works correctly. (Light is on/off when switch is on/off.)

How can he find the answer in the fewest trips between the switches and the lights without help? 

Which switch, which light?
Which switch, which light?

 

Solution:

Turn switch “1” on and leave it.

Leave switch “3” off.

Turn switch “2” on for a minute, then leave off.

Quickly go to the bulbs.

Label the on bulb “1”.

Label the off bulb that is still warm “2”.

Label the off bulb that is cold “3”.

Bridge Crossing Puzzle

Four people need to move from one side of a bridge to the other at night.

Each can cross at different speeds: 1, 2, 5, and 10 min.

There is only one flashlight and it must be carried each time someone crosses the bridge.

The bridge will only support two people at a time.

Two crossing together move at the slower speed of the two.

You cannot throw it across to your friends on the other side.

What is the shortest time required to get all 4 to the other side?

How quick across?
How quick across?

 

Solution:

Obvious answer: Have fastest escort others takes 19 min.

17 min solution: 1 escorts 2 and returns, 5 escorts 10 and 2 returns, and 1 escorts 2 to complete.

17 minute solution
17 minute solution

Three Hat Puzzle

As three people enter a room, a hat is placed on each head.

The color of each hat (red or blue) is determined by a coin toss.

Each can see the other hats, but not his own.

They are not allowed to communicate once the game begins.

After looking at the other hats, all must simultaneously guess the color of their own hats or pass.

The group shares a big prize if at least one guesses correctly and none guess incorrectly.

For example, if one guesses “Red” and others “pass” gives 50% chance.

What strategy should the three agree on to maximize their chances?

What color is my hat?
What color is my hat?

 

Solution:

If you see 2 red hats, then guess that yours is blue.

If you see 2 blue hats, then guess that yours is red.

Otherwise, you see one red and one blue, then pass.

Your team of 3 will only fail if all hats are red or all are blue.

You lose 2 out of 8 possible outcomes, your chances of winning are 75%.