Programmeeruitdaging

Programmeeropdracht

Beste ICTScripters,

Programmeren is vaak voornamelijk zoeken naar oplossingen. En dat is nu ook net wat de meeste mensen er zo leuk aan vinden! Om jullie programmeerkunsten te stimuleren heb ik voor jullie een leuke opdracht:

Schrijf van een gegeven getal alle mogelijke manieren om het getal te vormen uit de som van positieve naar het scherm. Als voorbeeld voor het getal 4:
4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

En voor het getal 6:
6
5 + 1
4 + 2
4 + 1 + 1
3 + 3
3 + 2 + 1
3 + 1 + 1 + 1
2 + 2 + 2
2 + 2 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1

Het doel is uiteraard een programma te schrijven wat gegeven een getal het getal zoals hierboven uitschrijft op het scherm. In PHP zou dat er als volgt uit kunnen zien:

<?php


function get_numbers($number) {
	//hier de logica
}


get_numbers(4);
get_numbers(6);


?>

De oplossingen mogen jullie naar mij toe sturen en die zal ik dan over ongeveer een week publiceren! En let op: Hoe minder code, hoe beter! Houd het script echter wel netjes. Creatieve oplossingen worden gewaardeerd. Oplossingen mogen in alle mogelijke programmeertalen geschreven zijn.

Veel succes en plezier! En denk eraan, je antwoord naar mij opsturen via PB, niet in dit topic posten! Meld het daarnaast even in dit topic als je meedoet!

Mijn oplossing bevat 8 regels code (in de functie, inclusief sluit-accolades). Omdat het moeizaam gaat een kleine typ:

Recursie!

Ik heb het op heden nog geen enkele oplossing mogen ontvangen! Jammer, had meer verwacht! Wie gaan het nog proberen?

Citaat van bramieboy100

Ik niet, het is een onmogelijk opdracht omdat er ontelbaar veel getallen zijn. Zelfs met recursie lukt dit niet.

Dat is zeker niet het geval. Als ik het afdrukken van de oplossing (wat verreweg het meeste tijd kost) achterwege laat, dan is het voor het getal 50 bijvoorbeeld in ongeveer een seconde uitgerekend. En dat is dan in PHP, een taal als Java of zelfs C is nog vele malen sneller.

Daarbij gaat het ook niet zozeer om de performance. Het is eigenlijk helemaal geen moeilijke opdracht!

Het is gelukt! Ik heb de eerste werkende oplossing ontvangen van EternalFlamez. Hoewel zijn oplossing lang niet de meest efficiënte is (in regels code), ben ik wel positief verrast. Het ziet er netjes uit, en er is duidelijk tijd aan besteed, mijn complimenten!

Dus, iedereen die niet met een valide oplossing kan komen is wat mij betreft een mindere programmeur dan EternalFlamez.

Wie gaan het nog meer proberen?

@Fils: Het stukje sarcasme leek me wel duidelijk, maar goed.

Ik heb inmiddels ook een mooie oplossing van victor gekregen. Met veel gepruts heb ik op de macbook van een vriend van me de code kunnen uitvoeren :P. De hoeveelheid code is lekker compact, maar de oplossing geeft helaas wel dubbele oplossingen (ook 1 + 1 + 3 bijvoorbeeld terwijl alleen 3 + 1 + 1 erin hoort te staan). Ik zal morgen nog eens iets beter naar de oplossing kijken, want hij ziet er wel interessant uit. In ieder geval ook voor deze oplossing mijn complimenten!

Het is tijd op de oplossing prijs te geven. Ik zal beginnen met de oplossing van EternalFlamez. Deze oplossing geeft het juiste resultaat, en er is geen gebruik gemaakt van recursie.

<?php
$arr = array(7);


base();


function base() {
	global $arr;
	show();
	while(getLastNotOne() != -1) {
		doItAll();
		show();
	}
}


function doItAll() {
	global $arr;
	$c = count($arr);
	//Pakt achterste waarde die groter is dan 1
	$i = getLastNotOne();
	
	//Verkleint het getal gevonden op pos $i. (4 -> 3 + 1 // 3 -> 2 + 1 // 2 -> 1 + 1)
	array_splice($arr, $i, count($arr) - $i, decreaseAtPos($arr, $i));
	
	//Als er een getal groter is dan de 1e is het een duplicaat (4 + 2 == 2 + 4)
	while(isOneLargerThanPrev() != -1) {
		$k = isOneLargerThanPrev();
		//Als het een duplicaat is dan moet er gewoon doorgegaan worden.
		array_splice($arr, $k, count($arr) - $k, decreaseAtPos($arr, $k));
	}
}


//Er wordt een subarray gemaakt van $arr die begint op $pos. 
//Als alleen de 1e geen 1 is, worden ze samengevoegd. (Zie count_ones())
//Anders wordt de 1e waarde verlaagd, en een 1 toegevoegd aan het einde van de array.
//Bijv: $arr = array(4, 2, 1); De subarray wordt array(2, 1), die wordt dan door deze functie array(1, 1, 1).
//Dit wordt dan weer teruggevoegd in de originele array, waardoor het array(4, 1, 1, 1) wordt.
function decreaseAtPos($arr, $pos) {
	$arr = array_splice($arr, $pos);
	if(count($arr) > 1) {
		$c = count_ones();
		
		if($c == count($arr) - 1) {
			array_splice($arr, 1, count($arr), array($c + 1));
		}
		else {
			array_push($arr, 1);
		}
	}
	else {
		array_push($arr, 1);
	}
	
	$arr[0]--;
	return $arr;
}


//Displayt de array.
function show() {
	global $arr;
	$count = count($arr);
	$text = '';
	for($i = 0; $i < $count; $i++) {
		if($i != 0) {
			$text .= ' + ';
		}
		
		$text .= $arr[$i];
	}
	
	echo($text. '<br/>');
}


//Returnt achterste waarde die groter is dan 1.
function getLastNotOne() {
	global $arr;
	$c = count($arr);


	for($i = $c - 1; $i >= 0; $i--) {
		if($arr[$i] != 1) {
			return $i;
		}
	}
	
	return -1;
}


//Telt aantal enen om te mergen zodra het klaar is met een reeks.
//Bijv: (4 + 2 => 4 + 1 + 1 => 3 + 3)
function count_ones() {
	global $arr;
	$r = 0;
	$c = count($arr);
	for($i = 0; $i < $c; $i++) {
		if($arr[$i] == 1) {
			$r++;
		}
	}
	
	return $r;
}


//Kijkt of de waarde al langs is geweest. Returnt -1 als het niet zo is, anders getLastNotOne().
function isOneLargerThanPrev() {
	global $arr;
	$c = count($arr);
	$smallest = $arr[1];
	
	for($i = 1; $i < $c; $i++) {
		if($arr[$i] > $smallest || $arr[$i] > $arr[0]) {
			return getLastNotOne();
		}
		else {
			$smallest = $arr[$i];
		}
	}
	return -1;
}
?>

De oplossing van victor geeft op dit moment nog niet exact het juiste resultaat. Hij is er nog mee bezig en wil dat nog oplossen. Zijn oplossing geeft wel alle oplossingen maar enkele dubbele (2 + 1 + 1 en 1 + 2 + 1 bijvoorbeeld). Zijn oplossing is (tot nu toe) als volgt:

<?php


function get_numbers($getal)
{


    $oplossingen = array();


    if($getal == 1)
    {
    
        array_push($oplossingen, '1');


    }


    for($i = 1; $i < $getal ; $i++)
    {


        foreach(get_numbers($getal-$i) as $oplossing)
        {


            array_push($oplossingen, $oplossing.'+'.$i);
        
        }
    
    }
    
    array_push($oplossingen, $getal);
    $oplossingen = array_unique($oplossingen);


    return $oplossingen;


}


echo '<pre>';


print_r(get_numbers(4));


echo '</pre>';


?>

Dan als laatste nog mijn eigen oplossing, die wel gebruik maakt van recursie:

<?php


function getPartitions($number, $previous = -1, $prefix = "") {
	if($number <= $previous || $previous == -1) {
		echo $prefix . $number . "<br />\n";
	}
	for($i = 1; $i < $number; $i++) {
		if(($number - $i) <= $previous || $previous == -1) {
			getPartitions($i, ($number - $i), $prefix . ($number - $i) . " ");
		}
	}
}


echo getPartitions(7);

Wat vinden jullie van de oplossingen? En wat vinden jullie van de uitdaging? Is dit voor herhaling vatbaar? Zou je wel meedoen als de opdracht makkelijker is (mocht je nu niet hebben meegedaan)? Ik hoor graag feedback!

Tim: Method overloading is toch niet zo bijzonder?

Maar aan het gebrek aan reacties te zien hoef ik dit dus niet nogmaals te doen?