Adobe Interview question - heuristic solution

Here's an easy solution (solutions are easy if the problem is hard because you don't have to try too hard since it will be very difficult to prove your solution isn't worse than an alternate)

1. Choose some number k < N the number of points
2. Choose the k closest pairs and connect them.
3. for each of the rest of the points, find the closest one to one of the endpoints of the k groups and add it in. Also include the endpoints of the groups (this results in a merge)
4. Repeat until all points added in.
5. Find "closest" group pairs and merge them. The closest group pair is the pair that can be merged with the least increase to the distance (you can connect endpoints, or do variations where you cut the groups in half and glue the 2 halves to another group).
6. Repeat (5) until all groups merged.

7. Repeat 1-6 experimenting with different values of k.

8. Simmer well until done to taste :)

Adobe Interview question

Here's an interview question, apparently from Adobe, posted on the Joel On Software site.

Someone ("d" is his moniker) posted that this was NP-complete. I think in this case the problem is to come up with an imaginative heuristic solution that will sound good to the interviewer :)

Adobe Interview Question

You are given a plotter which can plot points provided to it in the form of 'x' and 'y' coordinates. The plotter hand can move horizontally or vertically only. Your program will be given a list of 'n' coordinates in the form of {(x1,y1), (x2,y2} ... (xn,yn)}. Your program must print a sorted list of all 'n' points that would represent the least cumulative distance for the plotter hand to plot all 'n' points in that sorted order.

Inheritance of forms in VB .NET

In an earlier post, I talked about form to form navigation. An earlier version of this attempt tried to use in the built-in Form inheritance, which didn't work very well.

The form to form navigation worked fine, but I still had a hankering for some form of inheritance as I found myself creating many variants of forms for entering e.g. a booking field, a container field, etc. (the application is designed to be on a touch screen, for unsophisticated users, so buttons are big and each form is used to enter just 1 field).

I seem to have come up with an alternate solution. The solution is to create a parallel hierarchy of classes of controllers, associated with a form, that do the control. These classes have none of the VB behind-code associated complexity, so inheritance works as expected without unexpected sideeffets.

So far I've created a FormController at the top of the hierarchy, with a TextFormController beneath that, and a specific BookingFormController. The VB Design class is associated with the TextFormController, and the BookingFormController overrides that class to instantiate the heading and to override the save/restore next/back button navigation.

This new idea seems to be working well, and I'll probably eviscerate the code and post the skeleton classes a bit later.

Larry Watanabe's Gearchart

Years ago I wrote a simple program for calculating the equivalent size wheel for a given set of gears. That piece of code worked it's way into a bicycle FAQ and will probably outlive anything I've ever written in terms of code or publications. You never know what you'll be known for :)

Here's the link (and the code). It took me about 5 minutes to write.

/*
The C Source for Larry Watanabe's gear chart program
Originally found at ftp://draco.acs.uci.edu/pub/rec.bicycles/gear.c

*/
/* gear.c - prints out a table of gear-inches.
*
* Example:
*
* Wheel outside diameter: 27
*
* Chainwheel teeth: 50 40 27
*
* Rear cog teeth: 13 15 17 19 21 27
*
*
* 50 40 27
* -------------------------------
* 13 103.85 83.08 56.08
* 15 90.00 72.00 48.60
* 17 79.41 63.53 42.88
* 19 71.05 56.84 38.37
* 21 64.29 51.43 34.71
* 27 50.00 40.00 27.00
*
* Larry Watanabe watanabe@cs.uiuc.edu 1994
*/

#include
#define MAXFRONT 3 /* max number of chainwheels */
#define MAXREAR 8 /* max number of rear cogs */
main()
{
int c;
int i, j;

double wheel_diameter; /* outside diameter of wheel */
int front[MAXFRONT]; /* number of teeth for front chainwheels */
int rear[MAXREAR]; /* number of teeth for rear cogs */
int frontn = 0; /* number of front sprockets */
int rearn = 0; /* number of rear sprockets */
double gear_inch; /* gear-inches of current combo */

printf("Wheel outside diameter: ");
scanf("%lf", &wheel_diameter);

printf("\nChainwheel teeth: ");

/* skip over junk to get to a digit */
for (c = getc(stdin); !isdigit(c); c = getc(stdin))
;
ungetc(c, stdin);

/* input chainwheel sizes */
for (;;) {
c = getc(stdin);
if (c == '\n')
break;
if (isdigit(c)) {
ungetc(c, stdin);
scanf("%d", &front[frontn++]);
}
}
/* input rear cog sizes */
printf("\nRear cog teeth: ");
for (;;) {
c = getc(stdin);
if (c == '\n')
break;
if (isdigit(c)) {
ungetc(c, stdin);
scanf("%d", &rear[rearn++]);
}
}
printf("\n\n ");
for (j = 0; j < frontn; j++)
printf("\t%4d", front[j]);
printf("\n-------------------------------\n");
for (i = 0; i < rearn; i++) {
printf("%5d", rear[i]);
for (j = 0; j < frontn; j++) {
gear_inch = wheel_diameter * front[j]/ rear[i];
printf("\t%3.1lf", gear_inch);
}
printf("\n");
}
}

code formatter for VB

Strangely, the simple left-justified code looks better in the blog than the properly indented code -- because the blog columns are so narrow (to allow space for google ads I suppose).

Maybe we need a code formatter for blogs?

I'm not going to waste the space on my 2 22" monitors by formatting for the web :) Anyone really interested can just cut and paste into Visual Studio if they need properly formatted code.

VB Form to Form Navigation

I'm creating a wizard type application in VB.NET. One form starts off, then the next button goes to the next form, and so on.

Amazingly (at least to me) there didn't seem to be an easy way to do this. I looked on the net and the solutions there seemed to use a lot of resources by basically keeping all forms that have ever been opened, and creating a new form as the navigation target without closing any old ones.

With people buying 4GB of RAM nowadays (probably we will be up to 100 GB as a standard configuration when you are reading this) it's probably no big deal. But my OC wants to close the no longer needed forms :)

Here's a way to do this - this is just 3 forms. Form1 can navigate to form2 by pushing the button, Form2 can navigate to Form3 by pushing the button, and Form3 closes the application when it's button is selected. I wanted to keep the code clear of distracting details, so I just used the default names etc. for the forms and buttons.

Option Strict On
Option Explicit On

Public Class Form1
    Public continuation As FormContinuation


    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        ' initialize the first continuation with Form2. 
        ' later forms in the sequence are responsible for setting the continuation
        ' on this form to whatever should follow before they close themselves.
        ' We will just keep on opening and displaying those forms until
        ' someone sets it to nothing, after which the application will just
        ' close itself.
        continuation = New Form2
        Me.Hide()
        While Not continuation Is Nothing
            continuation.mainForm = Me
            continuation.showFormDialog()
        End While
        ' no more continuations, so just close this (the startup form)
        Me.Close()
    End Sub

    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        Dim pt As New Point With {.X = 0, .Y = 0}
        Dim sz As New Size With { _
            .Width = Screen.PrimaryScreen.Bounds.Width, _
            .Height = Screen.PrimaryScreen.Bounds.Height _
            }
        Me.Size = sz
        Me.Location = pt
    End Sub
End Class

Public Class Form2
    Implements FormContinuation

    Private m_mainForm As Form1

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click
        ' we want the application to continue with Form3,
        ' so just set that in the mainform and then close this form
        mainForm.continuation = New Form3
        Me.Close()
    End Sub

    Private Sub Form2_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load

    End Sub

    Public Property mainForm() As Form1 Implements FormContinuation.mainForm
        Get
            Return m_mainForm
        End Get
        Set(ByVal value As Form1)
            m_mainForm = value
        End Set
    End Property

    Public Sub showFormDialog() Implements FormContinuation.showFormDialog
        Dim pt As New Point With {.X = 0, .Y = 0}
        Dim sz As New Size With { _
            .Width = Screen.PrimaryScreen.Bounds.Width, _
            .Height = Screen.PrimaryScreen.Bounds.Height _
            }
        Me.Size = sz
        Me.Location = pt
        ShowDialog()
    End Sub
End Class

Public Class Form3
    Implements FormContinuation

    Private m_mainForm As Form1


    Private Sub Form3_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load

    End Sub

    Public Property mainForm() As Form1 Implements FormContinuation.mainForm
        Get
            Return m_mainForm
        End Get
        Set(ByVal value As Form1)
            m_mainForm = value
        End Set
    End Property

    Public Sub showFormDialog() Implements FormContinuation.showFormDialog
        Dim pt As New Point With {.X = 0, .Y = 0}
        Dim sz As New Size With { _
            .Width = Screen.PrimaryScreen.Bounds.Width, _
            .Height = Screen.PrimaryScreen.Bounds.Height _
            }
        Me.Size = sz
        Me.Location = pt
        ShowDialog()
    End Sub

    Private Sub Button3_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button3.Click
        ' This is the last form in the sequence, so set the continuation to
        ' Nothing before closing
        mainForm.continuation = Nothing
        Me.Close()
    End Sub
End Class

Option Strict On
Option Explicit On

Public Interface FormContinuation

    ''' <summary>
    ''' Get/set the mainForm of the series of forms
    ''' </summary>
    Property mainForm() As Form1

    ''' <summary>
    ''' Show the dialog. This allows initialization to be 
    ''' done before showing the dialog and to declare the
    ''' continuation as a FormContinuation yet still show the
    ''' dialog.
    ''' </summary>
    Sub showFormDialog()

End Interface

Code formatter for VB, C# to XML for blogging

Found a great code formatter for formatting VB/C# code in xml format so it can be published in a blog -- no more ugly left-justified code!

http://www.manoli.net/csharpformat