Kategoriarkiv: Programmering

Diverse programmeringsrelaterede artikler

Google Treasure Hunt 2008 - Del 2

21. maj 2008 Jakob Justsen 1 kommentar

Så har Google publiceret spørgsmål 2 i skattejagten, og igen har Hinnerup Net ApS lagt sig ud med det nye spørgsmål.

Denne gang får man en zip-fil til download. Zip-filen indeholder en katalog struktur, med en masse små filer. Hver fil består af et begrænset antal linjer, og på hver linje står et tal. Der gives to kritierier A og B til udvælgelse af tal i filerne. Hvert kriterie består af en delstreng som filens sti eller navn skal indeholde, en fil type samt et linje nummer. Opgaven går i al sin enkelthed ud på at summere tallene der opfylder kriterie A og derefter B. Det endelige resultat er produktet af de to summer.

På forundelig vis ender svaret endnu engang op med at være præcis 42 linjer langt.

Klik her for at se Java koden – spoiler advarsel!

package GoogleTreasureHunt2008;
import java.io.*;
import java.math.BigInteger;
import java.util.regex.Pattern;

public class GoogleTreasureHunt2 {
  public GoogleTreasureHunt2(String path, String a1, String b1, int l1, String a2, String b2, int l2) {
    File root = new File(path);
    System.out.println(sum(root, p(root, a1, b1), l1).multiply(sum(root, p(root, a2, b2), l2)));
  }	
  private Pattern p(File root, String a, String b) {
    String pattern = root.getAbsolutePath() + "\\.*" + a + ".*" + b + "$";
    return Pattern.compile(pattern.replace("\\", "\\\\"));
  }	
  private BigInteger sum(File dir, Pattern criteria, int line) {
    BigInteger result = BigInteger.ZERO;
    File[] files = dir.listFiles();
    for (File file : files)
      if (file.isDirectory())
        result = result.add(sum(file, criteria, line));
      else if (criteria.matcher(file.getAbsolutePath()).matches())
        result = result.add(lineToNumber(file, line));
    return result;
  }
  private BigInteger lineToNumber(File file, int line) {
    String l = null;
    BufferedReader reader = null;
    BigInteger result = BigInteger.ZERO;
    try {
      reader = new BufferedReader(new FileReader(file));
      for (int i = 1; (l = reader.readLine()) != null; i++) if (i == line) {
        result = new BigInteger(l);
        break;
      }
    } catch (Exception e) { ; }
    finally { try { reader.close(); } catch (Exception e) { ; } }
    return result;
  }
  public static void main(String[] args) {
    new GoogleTreasureHunt2("level2", "abc", ".pdf", 5, "yz1", ".pdf", 4);    
  }
}

Java, Programmering

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!"