Patroon-algoritme

[Verwijderd]

Hi,
ben bezig met een prive-project.
Nou zit ik een beetje vast met een algoritme voor het volgende (wordt overigens geschreven in Java, maar dat maakt voor het algoritme niet al te veel uit denk ik).

In feite is het een ministeck-patroon-generator
Als eerste zit ik met de verdeling van de mogelijke steentjes (vierkant, hoek, tweetjes, etc). Deze komen in een bepaalde verhouding voor. Hoe kan ik er nou voor zorgen dat de stenen ook in die verhouding worden gekozen?

Ik zei als eerste, er zijn dus nog meer problemen, maar daar kan ik denk ik wel uitkomen als ik hier een oplossing voor heb.

Iemand een idee?
Ik zat evt te denken aan een array met daarin de aantallen per soort steentje en dan array 1 voor 1 aflopen en telkens waarde 1 verminderen tot je bij 0 uitkomt. Lijkt me niet echt ideaal tho..

[whoami]

Ik snap jouw probleem niet echt.... Wat wil je precies? Waar zit het probleem? Kun je wat meer info geven.... De verdeling van de steentjes -> over wat moet je ze verdelen ? ....

Wat is een 'ministeck-patroon-generator', etc....

[Arnaud]

Simpele (snelle) methode: Kijk welke steentjes op een locatie zouden passen. Houd van alle soorten steentjes bij hoeveel er nog geplaatst moeten worden. Als op een lokatie meerdere steentjes passen kies je degene waar er nog de meeste van zijn.

Ingewikkelde (efficientere) methode: Kijk welke steentjes op een locatie zouden passen. Geef ieder soort steentje dat op deze lokatie past een waardering/wegingsfactor gebaseerd op zijn "optimaalheid" op deze plaats EN het aantal van dit soort steentjes dat er nog is. Plaats het steentje met de hoogste waardering/wegingsfactor.

[Verwijderd]

whoami schreef op 08 March 2003 @ 16:04:
Ik snap jouw probleem niet echt.... Wat wil je precies? Waar zit het probleem? Kun je wat meer info geven.... De verdeling van de steentjes -> over wat moet je ze verdelen ? ....

Wat is een 'ministeck-patroon-generator', etc....

de TS heeft een x aantal soorten steentjes, welke in een bepaalde verhouding in een grote bak voorkomen (dus uhm.. voor elke witte, bijvoorbeeld twee rode, etc).

Ministeck, dat zijn van die kleine plastic steentjes die je op een daarvoor speciaal gemaakte plastic plaat kan leggen. Het lijkt op een mosaic, je zou het kunnen vergelijken met uhmm..borduren met plastic

voor de TS:

Verwijderd schreef op 08 March 2003 @ 16:02:Ik zat evt te denken aan een array met daarin de aantallen per soort steentje en dan array 1 voor 1 aflopen en telkens waarde 1 verminderen tot je bij 0 uitkomt. Lijkt me niet echt ideaal tho..

Dat valt mee hoor, ik heb die manier ook wel eens gebruikt om blokjes voor een spel samen te stellen.

Wat je ook zou kunnen doen, is stellen dat voor elke ministeck-element A, er 2 elementen B zijn, 5 elementen C, etc. En dan net zolang doorgaan totdat je het maximaal aantal elementen hebt bereikt.

Of stellen dat je in totaal X elementen nodig hebt, en per element uitrekenen hoeveel er van dat soort moeten zijn (dmv procenten bijv.)

[Verwijderd]

Arnaud schreef op 08 March 2003 @ 16:13:
Simpele (snelle) methode: Kijk welke steentjes op een locatie zouden passen. Houd van alle soorten steentjes bij hoeveel er nog geplaatst moeten worden. Als op een lokatie meerdere steentjes passen kies je degene waar er nog de meeste van zijn.

Ingewikkelde (efficientere) methode: Kijk welke steentjes op een locatie zouden passen. Geef ieder soort steentje dat op deze lokatie past een waardering/wegingsfactor gebaseerd op zijn "optimaalheid" op deze plaats EN het aantal van dit soort steentjes dat er nog is. Plaats het steentje met de hoogste waardering/wegingsfactor.

Sounds interesting. Enige waar deze geen rekening mee houdt is bijvoorbeeld het feit dat je bij ministeck niet 4 vierkantjes op rij zou tegenkomen, ook al passen er allemaal vierkant.

Darthraider:
Dat met die procenten (geldt overigens ook voor Arnaud) is wat moeilijk voor te stellen. Tis al weer ERG lang geleden dat ik wiskunde heb gehad :]
*schaam*

nog eens goed nadenken over wat jullie zeggen, nog wat moeilijk voor te stellen (qua code dan, het principe daarvan)
Ben niet zo'n ster in coden :]

[bille]

bovengenoemde manier werkt wel.. alleen is niet echt objectgeorienteerd..

wat je kan doen is: maak een object "MinisteckstenenCollection" en die heeft een aantal functies bijvoorbeeld:

Java:

public boolean hasMinisteksteen(Color kleur, int type)

wil je het echt netjes doen dan maak je een MinisteckSteen class.... met attributen als kleur/type/plaats .. en dan vraag je aan je collectie een MinisteckSteen dmv getMinisteckSteen(Color kleur, int Type) .. krijg je dan een null terug.. dan heb je er dus geen meer.. of mocht het uitzonderlijk zijn dat je geen stenen meer hebt van een bepaalde kleur dan laat je een exceptie throwen..

TS: het is mij nog steeds niet helemaal duidelijk wat je precies wilt.. wil je vanaf een image (jpg/gif/bmp) een patroon maken?? Daar zijn namelijk al heel wat bekende algoritme voor.. worden ook gebruikt bij het maken ASCII art..
Bij ASCII art gaat het voorzover ik weet via grijswaarden ..

[ Voor 20% gewijzigd door bille op 08-03-2003 16:29 ]

[Verwijderd]

Verwijderd schreef op 08 March 2003 @ 16:21:
Darthraider:
Dat met die procenten (geldt overigens ook voor Arnaud) is wat moeilijk voor te stellen. Tis al weer ERG lang geleden dat ik wiskunde heb gehad :]

Voorbeeld, stel je hebt in totaal 100 ministeckjes (wat een woord ). Je stelt dat er 20% elementen van type A in moeten zitten, 15% elementen B, 45% elementen C, etc. Op die manier ligt (in dit voorbeeld) al vast dat er 20 elementen A zijn.

Ben niet zo'n ster in coden :]

Aldoende leert men

[Verwijderd]

bille schreef op 08 March 2003 @ 16:23:
bovengenoemde manier werkt wel.. alleen is niet echt objectgeorienteerd..

wat je kan doen is: maak een object "MinisteckstenenCollection" en die heeft een aantal functies bijvoorbeeld:

Java:

public boolean hasMinisteksteen(Color kleur, int type)

wil je het echt netjes doen dan maak je een MinisteckSteen class.... met attributen als kleur/type/plaats .. en dan vraag je aan je collectie een MinisteckSteen dmv getMinisteckSteen(Color kleur, int Type) .. krijg je dan een null terug.. dan heb je er dus geen meer.. of mocht het uitzonderlijk zijn dat je geen stenen meer hebt van een bepaalde kleur dan laat je een exceptie throwen..

TS: het is mij nog steeds niet helemaal duidelijk wat je precies wilt.. wil je vanaf een image (jpg/gif/bmp) een patroon maken?? Daar zijn namelijk al heel wat bekende algoritme voor.. worden ook gebruikt bij het maken ASCII art..
Bij ASCII art gaat het voorzover ik weet via grijswaarden ..

Ja ik wil idd vanaf een BufferedImage een patroon maken. Voor ministeck ben ik niet op de hoogte van een algoritme, maar het idee is ook zo'n beetje dat ik het zelf doe

Het probleem is meer die "hasMinisteckSteen()" dan het OO-gedeelte. Het gaat me dus meer om het idee erachter dan de daadwerkelijke implementatie.


Darthraider: aldoende leert men idd. Voor de uni moesten we java leren, en daar heb ik gewoon erg veel tijd ingestoken, en dat heb ik nu ook gehaald. Wil nu een practicum uitbreiden voor mijzelf met die ministeck-functie, omdat ik daar iemand blij mee kan maken. Ben dus aldoende aan't leren. Alleen zo'n algoritme bedenken is nog knap lastig :]
Vooral met gewogen zaken en verhoudingen enzo

[Knutselsmurf]

Ik neem aan dat je van bijv. een foto een ministeck-werkstuk wilt maken. De eerste stap is dan het ditheren van de afbeelding naar de beschikbare kleuren en afmeting. Zodra deze omgezette afbeelding vast ligt, moet je proberen om de ontstane vlakken zo optimaal mogelijk te vullen met de bechikbare steentjes. Hiervoor is bij mijn weten geen algorithme die gegarandeerd de ideale vlakvulling oplevert binnen een acceptabele tijd.

[Verwijderd]

knutsel: mjah wil niet vervelend zijn, maar dat heb ik allemaal al. Gaat mij om dat algoritme.

[Arnaud]

bille: De TS wil een algoritme schrijven dat zijn probleem oplost. Hoe je dat vervolgens oplost (recursie, functies, arrays, objecten, collections, exceptions, enz, enz) is totaal niet interessant. Uit ervaring zeg ik dat in dit geval "ouderwetse" arrays, (globale) variabelen, functies en recursie hier een makkelijke en snelle oplossing gaan vormen. OO-programmeren bied in dit geval geen meerwaarde en vereist meer programmeerervaring dan de TS lijkt te hebben.

TS: Als ik het goed begrijp wil je dus een pixelvorm zo goed mogelijk opvullen met een gegeven aantal steentjes. Mijn tips voor een algoritme heb je al. Uiteraard zal je voor dit soort (theoretische) zaken je wiskundekennis van stal moeten halen. Vergeet echter niet vooraf je gezonde verstand te gebruiken: Tel het aantal "witte" pixels en kijk of je daar wel voldoende steentjes voor hebt, doe hetzelfde voor rood, etc. Het is zo lullig als je een perfect algoritme hebt dat nooit resultaat zal geven omdat je gewoon te weinig steentjes hebt om je vorm te maken.

Ik kan me een hele tijd geleden nog een programmeerwedstrijd op GOT herinneren met een japanse puzzel erin. De kern hiervan, vlakjes vullen aan de hand van gegeven randvoorwaarden, komt overeen met jouw probleem. Ik denk dat je in dat topic nog wel wat inspiratie kunt opdoen

[ Voor 53% gewijzigd door Arnaud op 08-03-2003 17:05 . Reden: tips toegevoegd, Deleon verandert in bille ]

[Verwijderd]

arnaud: Ik *ben* de TS
En ik ben dus op zoek naar die oplossing, of dat met objecten of arrays en whatever gaat maakt me niet uit, als het maar werkt. Maar het grootste probleem is dus het algemene algoritme, ik denk dat ik't zelf wel kan omzetten naar imperatief/OO

[Arnaud]

Deleon: Je hebt helemaal gelijk, ik bedoelde Bille. Ik zal mijn post even aanpassen.

[Soultaker]

Je hebt bij ministeck toch ook eentjes, of niet? In dat geval zou ik gewoon beginnen met het at random plaatsen van de meeste moeilijke stukjes (hoekjes, vierkantjes) en dan steeds eenvoudigere stukjes (tweetjes) en tenslotte de overgebleven ruimte opvullen met eentjes. Aangenomen dat de hoeveelheid eentjes vrij groot is, kom je waarschijnlijk per toeval wel goed uit en in de juiste verhouding.

Een andere, misschien nog wel betere, methode, zou zijn om te beginnen met een veld met uitsluitend eentjes, en dan te bedenken hoeveel viertjes, hoekjes, etcetera je wilt hebben. Je gaat dan blokjes van vier eentjes vervangen door een viertje, etcetera, totdat de gewenste verhouding behaald is. Ook dit zou niet uit kunnen komen (in theorie) maar in de praktijk gaat 't misschien wel goed. Het mooie van deze methode is dat je kunt selecteren op kleur, en dus bij voorkeur eentjes samenvoegd die een gelijkende (of gelijke) kleur hebben. Het resulterende ministeckbord is dan een stuk mooier.

Een goed algoritme dat voor alle mogelijk verhoudingen en bordgroottes gegarandeerd gaat werken, bestaat niet, vrees ik.

[Verwijderd]

Actually, de eentjes zijn de minst voorkomende steentjes
Bordgrootte e.d. hoeven jullie je niet druk over te maken, dat kan ik zelf denk ik wel aardig oplossen

[Arnaud]

Het principe van Soultaker is heel erg quick-and-dirty en zal zeker geen optimale verdeling opleveren, MAAR als je voldoende steentjes hebt dan is het een hele snelle oplossing. Een voorbeeldalgoritme voor een situatie waarbij het er alleen maar om gaat het figuur op te vullen:

Veronderstelling: 1-tjes zijn makkelijk, 2-tjes zijn moeilijker, hoekjes nog moeilijker, t-tjes nog moeilijker, vierkantjes nog moeilijker, etc.
Vul eerst het hele figuur op met alle eentjes die je hebt.
Als er nog plekken zijn die niet opgevuld zijn dan ga je de eentjes zoveel mogelijk vervangen door 2-tjes.
Als er nog plekken zijn die niet opgevuld zijn dan vul je de figuur verder op met alle eentjes die je hebt.
Als er nog plekken zijn die niet opgevuld zijn dan ga je de eentjes en tweetjes zoveel mogelijk vervangen door hoekjes.
Als er nog plekken zijn die niet opgevuld zijn dan vul je de figuur verder op met alle eentjes en tweetjes die je hebt.
Etc.

[Rukapul]

Het is me niet helemaal duidelijk of er een benadering van kleuren moet plaatsvinden (bijvoorbeeld van true color naar de paar kleuren van ministeck kleuren) en dat de kleuren dus niet 100% hoeven te matchen.

Het lijkt me dat je voor je probleem een scoringsfunctie moet bedenken waarbij je goede en slechte oplossingen van elkaar kan scheiden. Typisch gezien kun je het globale optimum niet vinden met een dergelijk probleem, maar blijf je in een lokaal maximum hangen.

In de literatuur zou je eens kunnen kijken om enige algemene aanpakken voor dergelijke problemen op te zoeken, bijvoorbeeld hillclimbing of genetische algoritmen (hoewel ik nog geen idee heb hoe je het gen zou moeten coderen voor zo'n aanpak in dit geval) of simulated annealing.

[ Voor 3% gewijzigd door Rukapul op 08-03-2003 17:46 ]

[Knutselsmurf]

Verwijderd schreef op 08 March 2003 @ 17:14:
Actually, de eentjes zijn de minst voorkomende steentjes
Bordgrootte e.d. hoeven jullie je niet druk over te maken, dat kan ik zelf denk ik wel aardig oplossen

Ik zag dat er speciale strips te koop zijn met alleen maar 1-tjes.

Een mogelijke oplossing die globaal tot een redelijk verdeelde oplossing is het willekeurig kiezen van steentjes, met een kans die afhankelijk is van de verdeling van de steentjes op een strip. Doe dit een aantal keer, tel hetaantal benodigde strips en kies de meest gunstige. Deze methode zal niet de meest ideale oplossing geven, maar in soortgelijke gevallen gaf deze bij mij redelijke oplossingen binnen een redelijke tijd.

[Verwijderd]

Rukapul schreef op 08 maart 2003 @ 17:42:
Het is me niet helemaal duidelijk of er een benadering van kleuren moet plaatsvinden (bijvoorbeeld van true color naar de paar kleuren van ministeck kleuren) en dat de kleuren dus niet 100% hoeven te matchen.

Het lijkt me dat je voor je probleem een scoringsfunctie moet bedenken waarbij je goede en slechte oplossingen van elkaar kan scheiden. Typisch gezien kun je het globale optimum niet vinden met een dergelijk probleem, maar blijf je in een lokaal maximum hangen.

In de literatuur zou je eens kunnen kijken om enige algemene aanpakken voor dergelijke problemen op te zoeken, bijvoorbeeld hillclimbing of genetische algoritmen (hoewel ik nog geen idee heb hoe je het gen zou moeten coderen voor zo'n aanpak in dit geval) of simulated annealing.

Dat laatste gaat allemaal wat te ver
En de kleuren e.d. zijn allemaal al geregeld, het gaat dus puur en alleen om het verdelen van de steentjes.

Probleem is dus niet alleen de beste steentjes vinden, maar ook in de juiste verhouding en met de juiste verdeling.

[Verwijderd]

Knutselsmurf schreef op 08 March 2003 @ 17:43:
[...]

Ik zag dat er speciale strips te koop zijn met alleen maar 1-tjes.

Een mogelijke oplossing die globaal tot een redelijk verdeelde oplossing is het willekeurig kiezen van steentjes, met een kans die afhankelijk is van de verdeling van de steentjes op een strip. Doe dit een aantal keer, tel hetaantal benodigde strips en kies de meest gunstige. Deze methode zal niet de meest ideale oplossing geven, maar in soortgelijke gevallen gaf deze bij mij redelijke oplossingen binnen een redelijke tijd.

Die losse strips moeten we even buiten beschouwing houden, ik ga er van uit dat men gewoon een aantal kleurenstrips heeft. Ik kan op zich makkelijk genoeg uitrekenen hoeveel strips van welke kleur men nodig heeft (dat staat bij de gekochte patronen ook vermeld).

Jouw oplossing klinkt wel goed. Samen met een van de eerste vermeldingen. Ik kijk de discussie nog even aan (en doe actief mee natuurlijk), en dan ga ik't morgen ofzo gewoon proberen )

[Rukapul]

Verwijderd schreef op 08 March 2003 @ 19:13:
[...]


Dat laatste gaat allemaal wat te ver
En de kleuren e.d. zijn allemaal al geregeld, het gaat dus puur en alleen om het verdelen van de steentjes.

Probleem is dus niet alleen de beste steentjes vinden, maar ook in de juiste verhouding en met de juiste verdeling.

Het is me nu duidelijk. Je kunt het probleem dus onafhankelijk per kleur oplossen. Een iteratief proces (soort hillclimbing) lijkt me het beste aangezien het niet waarschijnlijk is dat je in een lokaal maximum vast komt te zitten door het type probleem.
Je begint met een willekeurige oplossing en vervolgens itereer je tot de toestand niet meer verbetert (bereken in hoeverre de verdeling overeenkomt met de verdeling van de stukjes aan een strip).
Een iteratie bestaat uit het vervangen van een groep stukjes door een andere groep stukjes die de verhouding verbetert.

[Soultaker]

Ik vind dat er zo hier en daar wat vreemde suggesties gegeven worden, maar misschien begrijp ik de aard van het probleem nog niet helemaal goed.

Hoe het ook zij; ik ben benieuwd hoe je uiteindelijke algoritme eruit komt te zien en wat je bevindingen daarmee zijn. Ik zou het op prijs stellen als je dat een beetje zou kunnen samenvatten, als je ermee klaar bent.

[Verwijderd]

Soultaker: will do! Zal de code wel posten ofzo. Kan helaas niet het hele project online zetten, omdat de rest volgend jaar als opdracht wederom gebruikt gaat worden op de uni.

De term "hillclimbing" ken ik niet, dus ik zal nog even op onderzoek uitgaan :]

[Verwijderd]

Heb inmiddels beginnetje gemaakt, maar wil nog niet helemaal lukken. Ben op dit moment maar een array aan't maken welke x,y,{kleurnr,patroonr} bevat. Nou nog patroonnummer gaan vullen Dan kan ik aan de hand van deze gegevens een nieuwe image tekenen..

Moeilijk. Probeer ff een vriend aan te schieten die wiskunde heeft gestuurd, misschien weet die nog wat Tis hier nogal stil ineens