Google Treasure Hunt 2008 - Del 1

18. maj 2008 Michael Fosgerau 2 kommentarer

Google har sat gang i en vaskeægte skattejagt. Hvad kisten indeholder er fornuværende stadig en velbevaret hemmelighed, og det famøse X på skattekortet jagtes af mange. Du kan selv deltage her og du kan læse mere om konkurrencen på denne side.

Første etape af udfordringen er at svare på hvor mange unikke stier der er for en robot der kun kan bevæge sig henholdsvist ned og mod højre, når denne starter i øverste venstre hjørne af et skakbræt af størrelsen W x H. Tallene W og H oplyses naturligvis forskelligt pr. forsøg man foretager.

Set fra et IT-synspunkt, er det fælles for løsningerne at det endelige tal overstiger almindelige heltals typer, så man skal benytte bit manipulation eller f.eks. BigInteger klassen fra Java for at kunne rumme det endelige tal.

Hinnerup Net ApS har hastigt strukket denne lille Java sag på 42 linier sammen, som kan løse opgaven uanset W og H (dog givet W og H er positive heltal):

Klik her for at se Java koden – spoiler advarsel!

package GoogleTreasureHunt2008;
import java.math.BigInteger;

public class GoogleBotSolver
{
  private BigInteger[][] results;
  public GoogleBotSolver(int w, int h)
  {
    results = new BigInteger[w][h];
    for (int x = 0; x < w; x++)
    {
      for (int y = 0; y < h; y++)
      {
        results[x][y] = null;
      }
    }
    System.out.println(C(w - 1, h - 1).toString());
  }
  private BigInteger C(int x, int y)
  {
    if (results[x][y] != null) return results[x][y];
    BigInteger res;
    if (x == 0 && y == 0)
    {
      res = BigInteger.ZERO;
    }
    else if (x == 0 || y == 0)
    {
      res = BigInteger.ONE;
    }
    else
    {
      res = C(x - 1, y).add(C(x, y - 1));
    }
    results[x][y] = res;
    return res;
  }
  public static void main(String[] args)
  {
    GoogleBotSolver gbs = new GoogleBotSolver(38, 58);
  }
}

Svaret for W=38 og H=58 som herover er 194937478788574958222679204. Så robotten har rigtigt nok et par muligheder at vælge imellem.

Opgaven er iøvrigt en velkendt afart af Pascal’s trekant.

JavaScript, Programmering

Klasser og klassenedarvning i JavaScript

11. apr 2008 Michael Fosgerau 2 kommentarer

Klassediagram Jeg havde i dag behov for at lære fra mig med hensyn til prototype’s JavaScript klasse implementation. Der er nogle udemærkede eksempler at finde men de var ikke optimalt nemme at forklare alle begreberne udfra – man skulle have lidt baggrundsviden med sig i hvert fald.

Det endte med at en mindre omskrivning af første eksempel på prototype hjemmesiden var alt der skulle til for at kunne formidle hvordan JavaScript klasser kan benyttes.

Her er det omskrevne eksempel, der blandt andet har flere instanser med og en lidt klarere constructor/super constructor illustration:

// Animal base class
var Animal = Class.create({
  initialize: function(type, name, sound) { // constructor
    this.type = type;
    this.name = name;
    this.sound = sound;
  },
  speak: function() {
    alert("The " + this.type + " named " + 
      this.name + " says " + this.sound);
  }
});

// Extended class (inherits from Animal)
var Dog = Class.create(Animal, {
  initialize: function($super, name) { // constructor
    $super("Dog", name, "Woof Woof!"); // call super class constructor
  },
  sit: function() { // extended function
    alert("The " + this.type + " named " + this.name + " is now sitting.");
  }
});

var duck = new Animal("Duck", "Daffy", "Quack!");
var dog1 = new Dog("Pluto");
var dog2 = new Dog("King");
duck.speak();
// --> alerts "The Duck named Daffy says Quack!"
dog1.speak();
// --> alerts "The Dog named Pluto says Woof Woof!"
dog2.sit();
// --> alerts "The Dog named King is now sitting."
dog2.speak();
// --> alerts "The Dog named King says Woof Woof!"

Gode råd

Er du opdateret?

13. mar 2008 Michael Fosgerau 1 kommentar

Et utal af hjemmesider kommer til på Internettet hver eneste dag. De fleste er små private blogs og mini-sider som kun har en stærkt begrænset bruger/læser skare. Men der findes også den del af nettet som bliver godt besøgt. Uagtet om man driver en hjemmeside med få besøgende pr. år eller flere tusinde pr. time er det vigtigt at have for øje at man dermed også bør tænke over hvad det er disse besøgende får serveret.

Har man ikke beskyttet sin server, hjemmeside, blog eller content-management system grundigt nok kan det gå galt.

Hvor galt det kan det da gå?

Advarsel: Links til eksterne sider fra dette punkt i artiklen kan lede til virusinficerede sider.

Et godt eksempel på dette er komikeren Omar Marzouk, der fornyligt har stiftet et parti kaldet Ny Filionggonggong som det kan læses på Politiken’s blog idag. Hjemmesiden er drevet af det vidt udbredte blogsystem WordPress. Desværre er der ikke tale om en opdateret udgave af WordPress, i skrivende stund er der anvendt version 2.3.2, hvilket har en række ærgelige konsekvenser. Dels er Omar Marzouk’s hjemmeside en fin og sikkert eftertragtet angrebsvektor for personer med urent mel i posen, da der er tale om en højt eksponeret hjemmeside der utvivlsomt har potentiale for at trække nogle tusinde besøg pr. dag. Problemet er at WordPress version 2.3.2 er sårbar overfor en række kendte angreb (hvilket v2.3.3 retter op på), der gør en kyndig angriber istand til helt at overtage hjemmesiden. Vedkommende vil kunne rette/slette indlæg efter eget forgodtbefindende.

Udover at være drevet af en ældre version af WordPress er der tilsyneladende også mangel på moderering af kommentarer på hjemmesiden. Dette har også en ubehagelig sideeffekt. I skrivende stund linkes der fra forsiden til ikke mindre end 5 forskellige virus inficerede eksterne hjemmesider fra boksen “Nyeste kommentarer”.

Min virus scanner rapporterede dette da jeg fulgte første kommentarlink:

Virus or unwanted program ‘HTML/Crypted.Gen [HTML/Crypted.Gen]’ detected in file ‘C:\Documents and Settings\Michael Schøler\Lokale indstillinger\Temporary Internet Files\Content.IE5\WVEVC6CT\songmlin9_forumup_ro[1].htm. Action performed: Deny access

Lektien ved dette

Der følger et “ansvar” med at drive en hjemmeside der tiltrækker mange besøgende kan man godt påstå. Ikke ment på den vis at der ville kunne gennemføres et juridisk gyldigt søgsmål mod det nye “partis” hjemmeside, men nærmere et professionelt stolthedsansvar. Man bør gøre sit ypperste for sikre ens server og ens besøgende ikke mindst.

Det er nemt at undgå

Det er relativt nemt i videst mulige udstrækning at sikre sig mod uforvarende at lede ens besøgende ind på inficerede sider og at have sikkerhedshuller i ens server/software, ved at følge disse simple grundregler:

Hold server og software opdateret
Anvend en virusscanner
Moderer alle kommentarer og/eller beskyt gerne mod anonyme kommentarer
Brug gerne anti-spam og captcha plugins på blog og CMS systemer
Gennemgå ofte hjemmesiden i sikkerhedsøjemed
Følg med på supportsiderne for de software-produkter der anvendes og tilmeld alle eventuelle sikkerhedsmailinglister