Programmeeruitdagingen topic

[Kravitz]

Uitdaging 2 heeft overigens weinig met programmeren te maken, ...

Heb je eigenlijk wel gelijk in.

In eerste instantie leek uitdaging 1 (toen ik de vraag maar half begreep) bijzonder simpel. Vandaar mijn snelle reactie en het volgende invuloefeningetje. Later bleek de zaak toch iets complexer. Om die reden zou ik het ook niet erg vinden moest iemand van jullie (met duidelijk veel meer ervaring) de volgende uitdaging naar voor brengen. Een gewaagder alternatief is natuurlijk ook goed.

[317070]

Ik denk dat mijn algoritme een complexiteit O(n³) (met n het aantal raketten). Dat is dus uiteraard stukken beter dan O(2ⁿ) bij het domweg nagaan van alle mogelijkheden.

PS: wie verzint een oplossing met backtracking voor de eerste uitdaging?

Ik heb op de trein iets bedacht dat zou moeten worstcase draaien in O(n²). Ik vermoed dat worstcase O(n.log(n)) ook mogelijk moet zijn, maar dat ga ik moeten uitschrijven om te kijken of ik in mijn telling niets over het hoofd gezien heb.

[Rogier]

Nog een snellere variant in PHP:

Verborgen inhoud

[pre]function MaxRockets( $rockets )

{

$solutions = array();

$maxLen = 0;

foreach($rockets as $height)

{

$bestSolution = $bestLen = -1;

foreach($solutions as $i=>$s)

{

$len = $index = count($s);

while($index>0 && ($prec=$s[$index-1])<$height) $index--;

if ($index>0 && $prec==$height) continue;

if ($index>$bestLen || ($index==$bestLen && $index==$len-1)) { $bestSolution=$i; $bestLen=$index; }

}

if ($bestSolution<0) $solutions[] = array($height);

else

{

$len = count($solutions[$bestSolution]);

if ($bestLen==$len) $solutions[$bestSolution][] = $height;

elseif ($bestLen==$len-1) $solutions[$bestSolution][$bestLen] = $height;

else $solutions[] = array_merge(array_slice($solutions[$bestSolution],0,$bestLen),array($height));

$maxLen = max($bestLen,$maxLen);

}

}

return $maxLen+1;

}[/pre]

Een lijst van 2000 stuks duurt hiermee minder dan een seconde. Met die recursieve variant hoef je daar niet aan te beginnen

[jhnbk]

O(n³) is blijkbaar niet voldoende voor die lijst met 2000 raketten (Mijn python oplossing doet op mijn netbook in ieder geval niet minder dan een seconde op 2000 stuks.). Best een interessant probleem; hop naar een volgende uitdaging?

[Rogier]

Ok dan weet ik nog wel wat:

Uitdaging 3

• Gegeven: een string (of array van karakters, afhankelijk van je favoriete programmeerdialect).
• Gevraagd: alle permutaties, oftewel alle mogelijke woorden die met de letters uit de gegeven string gemaakt kunnen worden (volgorde niet van belang).

Voorbeeld:

input = "test"

output = test, tset, stet, etst, sett, estt, tste, stte, ttse, tets, etts, ttes

Omdat het aantal mogelijkheden nogal groot wordt bij lange strings, laten we zeggen dat de gegeven string beperkt is tot maximaal 9 karakters lang.

[jhnbk]

Daar bestaan uiteraard gekende algoritmen voor. Aangezien ik die niet ken ga ik morgen eens kijken wat ik kan verzinnen.

[Drieske]

Trekt zeer fel op een (oud) opdrachtje uit mijn cursus Beginselen van Programmeren . Bij deze dan ook mijn 'poging' in Java. Of het optimaal is enzo, weet ik niet . Complexiteitsberekeningen zijn helaas men ding niet, dus dat laat ik aan anderen.

Verborgen inhoud

Code: Selecteer alles

import java.util.*;

public class PermutatieVb {

public static void main(String args[]) throws Exception {

Scanner input = new Scanner(System.in);

System.out.print("Geef string: ");

String chars = input.next();

toonPermutaties("", chars);

}

public static void toonPermutaties(String st, String chars) {

if (chars.length() <= 1)

System.out.println(st + chars);

else

for (int i = 0; i < chars.length(); i++) {

try {

String newString = chars.substring(0, i) + chars.substring(i + 1);

toonPermutaties(st + chars.charAt(i), newString);

} catch (Exception e) {

e.printStackTrace();

}

}

}

}

[jhnbk]

Python:

Verborgen inhoud

Code: Selecteer alles

def anagrammen(woord):

a=['']

for x in range(len(woord)):

temp=[]

for anagram in a:

for letter in [i for i in woord if anagram.count(i)<woord.count(i)]:

if not (anagram+letter) in temp:

temp.append(anagram+letter)

a=temp[:]

return a

Helaas verre van efficiënt

[Rogier]

In php, enigszins geoptimized:

Verborgen inhoud

Code: Selecteer alles

function Anagrammen( $s )

{

 $n = strlen($s);

 $u = range(0,$n-1);

 for ($w=array();;$r='')

 {

  for ($i=0; $i<$n; $i++) $r .= $s[$u[$i]];

  if (!in_array($r,$w)) $w[] = $r;

  for ($i-=($k=1); $i<$n; $i+=1-$k)

  {

   if ($k && ++$u[$i]==$n) { if (!$i) return $w; $u[$i--] = 0; continue; }

   for ($j=$k=0; $j<$i; $j++) if ($u[$i]==$u[$j]) { $k = 1; break; }

  }

 }

}

Maar echte snelheidswinst is denk ik te halen door slimmer met dubbele letters om te gaan (d.w.z. slimmer dan botweg alle permutaties afgaan en kijken of je die al hebt gehad)

Ik vond die Haskell oplossingen van EvilBro trouwens wel fraai, zo kort & krachtig. Werkt dat nou nog enigszins efficiënt? Hoe lang doet de snelste Haskell variant bijvoorbeeld over een lijst van 10000 ?

En hoe zou een Haskell variant eruit zien van die permutatievraag? (waarschijnlijk 10x korter en leesbaarder dan die php-spaghetti hierboven..)

[EvilBro]

Ik vond die Haskell oplossingen van EvilBro trouwens wel fraai, zo kort & krachtig. Werkt dat nou nog enigszins efficiënt? Hoe lang doet de snelste Haskell variant bijvoorbeeld over een lijst van 10000 ?

Ik heb een random permutatie van de getallen 1 t/m 32768 gemaakt en daar de eerste 10000 van genomen. Oplossing 3 en 4 doen daar 2.2 seconden over. Dat is niet gecompileerd maar vanuit ghci (maar dat zal wel een of andere JIT-compilatie techniek gebruiken).

En hoe zou een Haskell variant eruit zien van die permutatievraag? (waarschijnlijk 10x korter en leesbaarder dan die php-spaghetti hierboven..)

Oplossingen voor uitdaging 3:

Verborgen inhoud

Code: Selecteer alles

import Data.List

-- using 'permutations'

solution1 = nub $ permutations "test"

-- using own permutation function

solution2 = nub $ perms "test"

where

perms (x:[]) = [[x]]

perms xs = concat [map (x:) (perms (xs \\ [x])) | x <- xs]

-- using own permutation function with nub in a better place

solution3 = perms "test"

where

perms (x:[]) = [[x]]

perms xs = concat [map (x:) (perms (xs \\ [x])) | x <- nub xs]

De eerste twee versies worden vrij snel onbruikbaar. De derde versie doet het veel beter.

[In physics I trust]

Uitdaging 4



Dominoblokjes hebben twee vierkantjes, en de blokjes uit tetris - genaamd tetrominos - hebben er vier: het zijn speciale gevallen van polyominos. In het algemeen is een polyomino een figuur die bestaat uit N vierkantjes die aan elkaar hangen doordat de vierkantjes een zijde gemeenschappelijk hebben.

Voor N = 2 bestaat er essentieel maar een polyomino (een domino dus).

De opdracht: Schrijf een programma dat bepaalt hoeveel verschillende polyominos er zijn voor een gegeven N. Twee polyominos zijn verschillend indien ze niet door een draaiing van 90 of 180 graden in elkaar kunnen getransformeerd worden.



De invoer is een geheel getal N in [1,10], dus inclusief 1 en 10. De output is een geheel getal.



Bron: Vlaamse Programmeerwedstrijd

[Rogier]

In het algemeen is een polyomino een figuur die bestaat uit N vierkantjes die aan elkaar hangen doordat de vierkantjes een zijde gemeenschappelijk hebben.

Ik neem aan dat dat kan worden opgevat als "minstens één zijde" ? (aangezien een 2x2 blok ook in tetris voorkomt)

Dus bijvoorbeeld een rechthoek van 4x3 blokjes is een geldige 12-omino?

[EvilBro]

Oplossingen voor uitdaging 3:

Verborgen inhoud

Code: Selecteer alles

-- not really different from solution3: avoids [x] construction.

solution4 = perms "test"

    where

        perms [] = [[]]

        perms xs = concat [map (x:) (perms (delete x xs)) | x <- nub xs]



solution5 = perms "test"

	where

		perms xs = traceThrough (createGraph xs) (sort xs)



createGraph xs = createGraph' Map.empty (sort xs) 

createGraph' m [] = m

createGraph' m xs = case (Map.lookup xs m) of

							 Nothing -> foldl createGraph' (Map.insert xs links m) (map snd links)

							 Just x  -> m

	where

		links = [(x, delete x xs)| x <- nub xs]



traceThrough _ "" = [""]

traceThrough m xs = concat [map (a:) (traceThrough m b) | (a,b) <- links]

	where

		Just links = Map.lookup xs m

Solution5 maakt een 'tree' (graph?) aan. Op deze manier voorkom je dat je twee keer alle permutaties van dezelfde elementen gaat bepalen. Voorbeeld: stel je begint met "test". Als je 't' en dan 'e' kiest houdt je hetzelfde over als je over zou houden door eerst 'e' en dan 't' te kiezen. Het nadeel van deze implementatie is dat je eerst de hele graph gaat bouwen. Je loopt daardoor waarschijnlijk sneller aan tegen geheugenproblemen.

[In physics I trust]

Ik neem aan dat dat kan worden opgevat als "minstens één zijde" ? (aangezien een 2x2 blok ook in tetris voorkomt)

Dus bijvoorbeeld een rechthoek van 4x3 blokjes is een geldige 12-omino?

Inderdaad, correccte toevoeging!

[Rogier]

Eerste poging voor nr 4:

Verborgen inhoud

[pre]class Coord

{

var $x,$y;

function Coord($x,$y) { $this->x=$x; $this->y=$y; }

function Copy() { return new Coord($this->x,$this->y); }

function Neighbors() { return array(new Coord($this->x-1,$this->y),new Coord($this->x+1,$this->y),new Coord($this->x,$this->y-1),new Coord($this->x,$this->y+1)); }

}

class Polyonimo

{

var $c=array();

function Copy() { $p=new Polyonimo; foreach($this->c as $q) $p->c[]=$q->Copy(); return $p; }

function Fix() { $p=$this->c[0]->Copy(); foreach($this->c as $q) { $p->x=min($p->x,$q->x); $p->y=min($p->y,$q->y); } foreach($this->c as &$q) { $q->x -= $p->x; $q->y -= $p->y; } }

function Rotate() { $b=$this->c[0]->y; foreach($this->c as $q) $b=max($b,$q->y); foreach($this->c as &$q) { $z=$b-$q->y; $q->y=$q->x; $q->x=$z; } $this->Fix(); }

function IsEqual($p) { if (count($this->c)!=count($p->c)) return false; foreach($this->c as $q) if (!in_array($q,$p->c)) return false; return true; }

function IsSimilar($p) { for($i=0; $i<4; $i++) { if ($i) $p->Rotate(); if ($this->IsEqual($p)) return true; } return false; }

function GetSurroundingCoords() { $a=array(); foreach($this->c as $q) { $r=$q->Neighbors(); foreach($r as $s) if (!in_array($s,$a) && !in_array($s,$this->c)) $a[]=$s; } return $a; }

function GetExtensions() { $a=array(); $b=$this->GetSurroundingCoords(); foreach($b as $p) { $q=$this->Copy(); $q->c[]=$p; $q->Fix(); $a[]=$q; } return $a; }

}

function GetAllPolyonimos( $n )

{

if ($n==1) { $p=new Polyonimo; $p->c[]=new Coord(0,0); return array($p); }

$a=array(); $p=GetAllPolyonimos($n-1); foreach($p as $q) { $e=$q->GetExtensions(); foreach($e as $r) { foreach($a as $s) if ($r->IsSimilar($s)) { $r=null; break; } if ($r) $a[]=$r; } }

return $a;

}

function CountPolyonimos( $n ) { return count( GetAllPolyonimos($n)); }[/pre]

Bepaald niet optimaal, bij n=10 duurt hij vervelend lang (uitkomst: 9189 )