Two Guys Arguing

A Solution from Purgatory (for the Matrix from Hell)

Posted in challenge, math, questions by benjaminplee on 01.02.11

This post attempts to recount some of my thought process which eventually (more than a year later) lead to the Matrix from Hell puzzle I posted about a few days ago.  If you don’t want to know my answer, don’t read the rest of this post.  My final solution is at the bottom.

You have been warned.

~~~~~~~~~~~~~~~~~~~

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

~~~~~~~~~~~~~~~~~~~

Below is a list of my general thought process and the main ideas/revelations/halucinations that I know helped me to my solution.  An annotated matrix is at the bottom with some of the ideas highlighted in different colors.

  • Should indices start at 0 or 1?
  • Values along either axis count up by 1 in both directions when the other =0
  • Values are duplicated over the f(x)=y axis –> Order of indices given to function is inmaterial since they can be swapped
    [The RED 5 can be seen duplicated over the diagonal]
  • Calculation of max/min index is O(1) so stop worry about it and “forget” the bottom half of the matrix (assume X>= Y)
  • Values generally increase as they go right/down but not always
  • f(x,x)=0, f(x,0)=x
  • Values are symmetrical perpendicular to f(x)=y IFF the bounding square in question is a power of 2
  • “Quad” patterns can be seen repeating for every power of 2.  In each “Quad” the top left quadrant is the same as the bottom right and the top right is the same as the bottom left.
    [Each "Quad" of the example matrix is outlined in BLUE with the quadrants in LIGHT BLUE. PINK shows the repetition]
  • power of 2 repeating nature of the values leads to thinking of binary trees
  • binary trees leads to thinking about a possible solution which could run in O(log2 n) time:
    • In a nut shell, for a given (X,Y), algorithm would find smallest boudning power of 2 including X and would walk back “Quad”s by each successivly smaller power of 2 “Quad” until the last one is met.  For each “Quad” determine which quadrant the value lives in and remap to root values.
    • Debate if this would really work for large numbers and if it could be reduced to constant time function by math that I have forgotton from college/HS
    • Dismiss b/c I can’t remember a way and base idea is > O(1)
  • Binary trace back algorithm idea makes me realize that it can be also looked at as the “binary” representation of a number (e.g. 01011011010) where each 1 represents a “Quad” where the value was in the upper right or bottom left and vica-verca.
    [Following the matrix value at (5,6) can be seen ORANGE.  The value 3 is in the bottom right  of the 1st "Quad", then BL, & TR. {BR BL TR} => {101} => {3}]
  • Remembered that f(x,y)=0 IFF x==y …. which means that difference between X and Y is important to value of f()
  • Eureka!
    • F(X, Y) = X xor Y
    • solution typed above in white on white to protect the innocent. highlight to view.

sample matrix with some of my thought process drawn out

That is it.  I never said it was pretty or made any sense.

Tagged with: , , , ,

C# Meta-Programming And Extension Methods Question

Posted in .net, functional programming, questions by benjaminplee on 12.30.10

First, it should be noted that my ASP.Net MVC-foo is yet great and I know this.  If you know a better way to do this, please take the time to explain how you are superior.  If you don’t, how will we ever know?

Working with ASP.Net MVC 2 client-side form validation this past week, I ran into two unfortunate (IMHO) facts which kept tripping me up:

  1. Html.ClientValidationEnabled() must be called as a scriptlet BEFORE the form is created
  2. Html.ValidateFor or Html.ValidationMessageFor must be called for EACH property of the model you want validated.

*** This StackOverflow answer includes a couple other important & useful things to note

These two issues (and many more) bother me about ASP.Net MVC 2 client-side validation but #2 in particular was really ticking me off.  I like that I can conditionally turn validation on/off on a field by field basis … but why make me enumerate all validation-needed model fields twice in my view!?  Especially in my case where I want validation turned on for ALL model object fields that have DataAnnotation Validations defined for.  Obviously the fields are going to be enumerated in the view once; how else are the text boxes and drop downs going to be created, but why make me list out each field AGAIN just to turn on validation?

All of this amounts to one WET solution. Am I missing something?

The best solution I have seen, and the one I am about to start implementing, is this one by Rick Anderson over at MSDN found via this related forum post.  The idea is to create additional Html helper extension methods which will combine the creation of the HTML form element with turning on and configuring validation.  This solution has the benefit of making me enumerate the model fields being used only ONCE in my view code and reads cleaner.

The only problem is that I have to walk through our application, find anywhere that is using a built in HtmlHelper extension method to build an HTML form element (e.g. input tag), build a new validating wrapper extension method that matches the signature of the original, and then replace the original code with the new extension method.  This can be done, but is time consuming and error prone.  And I am lazy.

The real issue …

I want to … create additional HtmlHelper extension methods based on all existing ones that produce form elements and take in a Linq expression to find the model property that first pass that expression to helper.ValidateFor() and then return the original extension method’s valued.

Is there any meta-programming feature or technique in C# that will allow me to concisely do that?

e.g.

Since Html.TextBoxFor(user => user.FirstName) is used in our app, as it stands I will am going to create a custom extension method similar to:

public static class ValidatingFormElementsExtension
{
  public static MvcHtmlString ValidatedTextBoxFor<TModel, TProperty>(this HtmlHelper<TModel> helper, Expression<Func<TModel, TProperty>> expression)
  {
    helper.ValidateFor(expression);
    return helper.TextBoxFor(expression);
  }

  // and so on for EACH one we use

}

Anyone have any ideas?  Am I completely off base with this? Is there a better way?

~~~~~~~~~~

<mini-related-rant>

A few more quick cracks at ASP.Net MVC  that I need to get off my chest

  • Why are so many things done in scriptlets!?  I feel like I am back in the vanilla JSP days of yesteryear.
  • They are Annotations in Java and Attributes in C# …. so why are the data validation attributes defined in System.ComponentModel.DataAnnotations?
  • I get that HTML checkbox form input fields have TRUE/FALSE values passed back when the form is submitted, and that doesn’t map perfectly to how other fields are handled by the Required attribute …. but why was NOTHING included to do this?  Having to use a RegularExpression validator for [Tt]rue is clumsy no?

</mini-related-rant>

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: