Archief - [PROG]Java code voor vier op een rij te detecteren

michael87 · 14 mei 2007

Hoy mensen,

Zit zo dat ik een manier heb bedacht om in het spel vier op een rij, uit te zoeken of er nu ergens vier schijven op een rij zijn gevormd. Nu ik vind dit nogal omslachtig, vroeg me af of dit ook korter kan genoteerd worden dan dit. Nu het moet ook niet moeilijker gaan worden, ik moet het ook nog begrijpen ook ( beginner).
Zoals u ziet is dit nog maar voor een 3 op 3 raster, dus voor een vier op een rij raster, dat 6op 7kolommen is wordt dit tamelijk veel.

Bovendien, ik veronderstel dat hij zal weten dat er vier schijven op een rij zijn gevormd, maar dit moet uiteraard ook vanéénzelfde kleur zijn (geel of rood). En dat vraag ik me ook af hoe ik dat in die test moet zetten. Of kan het zijn dat hij ook de kleur meepakt, dan klopt het verhaal?

Alvast bedankt voor de reacties

public void vierTest()
{
for(int i =0;i<3;i++)
{
//test verticals
if((map[0] | map[1] | map[2])>0)
if((canvas[0]==canvas[1])&(canvas[1]==canvas[2]))
winner=true;
//test horizontals
if((map[0] | map[1] | map[2])>0)
if((map[0]==map[1])&(map[1]==map[2]))
winner=true;
//test backward diagonal
if((map[0][0] | map[1][1] | map[2][2])>0)
if((map[0][0]==map[1][1])&(map[1][1]==map[2][2]))
winner=true;
//test foeward diagonal
if((map[2][0] | map[1][1] | map[0][2])>0)
if((map[2][0]==map[1][1])&(map[1][1]==map[0][2]))
winner=true;
}
}//end viertest

MilM · 14 mei 2007

Je moet niet telkens heel de map afgaan.
Als je een schijf laat vallen, volstaat het om te starten van die schijf.
Je controleert dus:
1) horizontaal (links en rechts)
2) naar beneden (boven kan niet)
3) diagonaal naar linksbeneden - rechtsboven
4) diagonaal naar rechtsboven - linksbeneden

(btw, controleren of ge einde van uw bord nie tegenkomt en rekening houdend met de kleur van de schijf)

1: maximum vier checks
2: maximum drie checks
3: maximum vier checks
4: maximum vier checks

Da zijn dus maximum 15 checks, ongeacht de grootte van uw bord. (constant dus)

EDIT: over datzelfde kleur, zo moeilijk is dat toch niet ?
Denk er eens wat over na

Timmos · 14 mei 2007

Het aantal if-en dat ge gebruikt wijst er alleszins op dat het geen goede manier is. En zoals MilM zegt, volstaat het om te vertrekken van de schijf die ge inwerpt (in de veronderstelling dat ge altijd een spel begint met een leeg bord).

Wat bij mij direct opkomt is met een while lus testen hoeveel aaneengesloten schijven er langs de ene kant liggen met dezelfde kleur als uw ingeworpen schuif, hetzelfde voor de overstaande kant van de ingeworpen schijf. Tel deze aantallen op, vermeerderd met 1 (de schijf zelf meetellen). Is deze uitkomst groter of gelijk aan 4 dan hebt ge een vier-op-een-rij.

Doe dit dan in de vier mogelijke richtingen indien ge nog geen 4 op een rij gevonden hebt, of indien ge van plan zijt om ze allemaal te zoeken.

Indien ge een rij vindt dan weet ge al direct wie de winnaar is ook, namelijk de huidige speler.

Timmos · 14 mei 2007

Ge kunt het eventueel ook nog wiskundig benaderen. Aangezien uw spelers door 1 en -1 worden voorgesteld (

)

Ge neemt de som van 4 aaneengesloten schijven waaronder uw ingeworpen schijf. Indien de absolute waarde van de som van deze 4 schijven gelijk is aan vier, dan hebt ge 4 op een rij. Daarna neemt ge een 'grensschijf' van deze 4 weg en voegt ge langs de andere kant een nieuwe 'grenschijf' toe. Ge trekt de waarde van de oude schijf af van de som, ge telt de waarde van de nieuwe schijf erbij en weer berekent ge de absolute waarde.

Voor slechts 4 op een rij is dit algoritmisch geen al te goede oplossing. Maar voor 1000 op een rij te zoeken in een veld dat al is opgevuld zou dit algoritme wel sneller werken, omdat het zich meer leent voor optimalisatie (wanneer een som op een bepaald moment kleiner is dan een bepaald getal kunt ge het zoeken in die richting afbreken omdat de absolute waarde van de som nooit 1000 zal bereiken).

Maar dit terzijde. Probeer die eerste mogelijkheid eens uit.

MilM · 14 mei 2007

Dit is niet sneller.
Je breekt nog altijd op hetzelfde moment de zoektocht af langs één kant af, namelijk wanneer je een kleur van de andere speler tegenkomt. Om daarna de andere kant uit te zoeken.

Tenzij ik nu te rap reageer en iets over het hoofd ziet, maar volgens mij gaat uw uitleg niet op.

Timmos · 14 mei 2007

Ik had het wel over een veld dat al IS opgevuld.

Het verschil zit hem in het testen. Bij de while controleert ge elke keer opnieuw of de kleur (de int) hetzelfde is, voor iedere schijf opnieuw. Bij de wiskundige oplossing moet ge evenveel schijven itereren, maar ge doet maar één if, namelijk na het optellen van de waarden van de schijven.

Ik dacht dat testen meer rekencapaciteit vroeg dan een gewone optelling

MilM · 15 mei 2007

Timmos zei:
Ik had het wel over een veld dat al IS opgevuld.

Wat bedoel je met een veld dat is opgevuld ?
Een veld waar je niet uitgaat van de laatste schijf ? (of één waar al enorm veel schijven in zitten)
Zoja, heeft dat weinig te maken met het (fictieve) spel duizend op een rij, want ook daar moet ge van de laatste schijf vertrekken.

Er is gelijk deel weg dat ook niet echt juist was é

(van die som groter dan 250)

MilM · 15 mei 2007

Timmos zei:
Ik dacht dat testen meer rekencapaciteit vroeg dan een gewone optelling

Dit zou best kunnen, maar daar ging uw post ook nie over é

Je begon over die reeks omdat je die zou kunnen afbreken op bepaald moment, terwijl het nog steeds hetzelfde afbreekpunt is als een andere methode

Het is dus niet alsof je meer kan gaan snoeien in uw controle. (wat toch wel uw opmerking was)

(tenzij ik nog steeds iets over het hoofd zie)

Timmos · 15 mei 2007

Er is inderdaad een stuk weg uit mijn post omdat ik geen zin heb om precies te zoeken bij welk getal je moet afbreken.

Ik had het over een volledig opgevuld veld ook, niet uitgaande van de laatst ingestoken schijf.

Kzal toch eens een voorbeeld proberen vinden

Stel ge hebt een rij van 1000 blauwe schijven en ge moet aantonen dat er 1000 dezelfde schijven in zitten. Bij de while gaat ge ze allemaal moeten afgaan, bij de for ook. Maar stel nu dat de 700e schijf een rode was. Dan hebt ge bij uw while 700 iteraties. Bij uw for maar 500, want ik start in de helft (500 is het centrum, 250-750). Mijn som is niet 500 maar 498. Dus moet ik niet meer verderzoeken.

Uitbreidbaar naar n-op-een-rij in een rij van m schijven waarbij n < m.

Maar toegegeven, het is zeker niet de moeite waard om te implementeren. Er zullen zeker situaties zijn waar de while dan rapper is. Dit voorbeeld is natuurlijk ook extreem gekozen.

Ik zou wel nooit de kracht van wiskunde in algoritmes onderschatten. We zien genoeg voorbeelden in onze lessen (Google's zoekalgoritmes en zo).

[BAT] Hydra · 15 mei 2007

Timmos zei:
Er is inderdaad een stuk weg uit mijn post omdat ik geen zin heb om precies te zoeken bij welk getal je moet afbreken.

Ik had het over een volledig opgevuld veld ook, niet uitgaande van de laatst ingestoken schijf.

Kzal toch eens een voorbeeld proberen vinden

Stel ge hebt een rij van 1000 blauwe schijven en ge moet aantonen dat er 1000 dezelfde schijven in zitten. Bij de while gaat ge ze allemaal moeten afgaan, bij de for ook. Maar stel nu dat de 700e schijf een rode was. Dan hebt ge bij uw while 700 iteraties. Bij uw for maar 500, want ik start in de helft (500 is het centrum, 250-750). Mijn som is niet 500 maar 498. Dus moet ik niet meer verderzoeken.

Uitbreidbaar naar n-op-een-rij in een rij van m schijven waarbij n < m.

Maar toegegeven, het is zeker niet de moeite waard om te implementeren. Er zullen zeker situaties zijn waar de while dan rapper is. Dit voorbeeld is natuurlijk ook extreem gekozen.

Ik zou wel nooit de kracht van wiskunde in algoritmes onderschatten. We zien genoeg voorbeelden in onze lessen (Google's zoekalgoritmes en zo).

Als gij dit probleem in kleiner dan O

kunt oplossen geef ik u 100€. Wat gij zegt is pure zever. De complexiteit van zoeken of elementen in een rij gelijk zijn is altijd O(lengte van de rij) hoe ge het ook draait of keert. Speciale truukskes zoals dingen beginnen optellen of in het midden beginnen kijken veranderen daar geen zak aan...

MilM · 15 mei 2007

Timmos zei:
Er is inderdaad een stuk weg uit mijn post omdat ik geen zin heb om precies te zoeken bij welk getal je moet afbreken.

Als je 10 op een rij moet hebben en je stelt rood = -1 en blauw = +1, dan breek je af op het moment dat je geen 10 meer kunt halen (zoals je zelkf zegt).
En wanneer is dit ? Juist, wanneer je een andere kleur tegenkomt.
Maw, precies op hetzelfde moment dan wanneer je via booleans werkt of via 1 en 2 (opv -1 en 1)

Kzal toch eens een voorbeeld proberen vinden

Best

Stel ge hebt een rij van 1000 blauwe schijven en ge moet aantonen dat er 1000 dezelfde schijven in zitten. Bij de while gaat ge ze allemaal moeten afgaan, bij de for ook. Maar stel nu dat de 700e schijf een rode was. Dan hebt ge bij uw while 700 iteraties. Bij uw for maar 500, want ik start in de helft (500 is het centrum, 250-750). Mijn som is niet 500 maar 498. Dus moet ik niet meer verderzoeken.

Dat is niet waar.
Als je met booleans werkt, kun jij evengoed in het midden starten.
Ik zal u een ander voorbeeld geven.
Stel dat die rode schijf op positie 2 zit, dan zal je er juist veel langer overdoen.
Dat heeft nu te maken met waar je start te controleren en niet hoe je het doet.

Ik zie trouwens niet in waarom je er in dit geval zelfs 500 controleert.
Je mag afbreken vanaf je het 700ste gecheckt hebt.

Ik zou wel nooit de kracht van wiskunde in algoritmes onderschatten. We zien genoeg voorbeelden in onze lessen (Google's zoekalgoritmes en zo).

Maar hier heb ik nog altijd geen wiskundig voordeel gezien om de complexiteit te verminderen.

Ice · 15 mei 2007

Timmos zei:
Er is inderdaad een stuk weg uit mijn post omdat ik geen zin heb om precies te zoeken bij welk getal je moet afbreken.

Ik had het over een volledig opgevuld veld ook, niet uitgaande van de laatst ingestoken schijf.

Kzal toch eens een voorbeeld proberen vinden

Stel ge hebt een rij van 1000 blauwe schijven en ge moet aantonen dat er 1000 dezelfde schijven in zitten. Bij de while gaat ge ze allemaal moeten afgaan, bij de for ook. Maar stel nu dat de 700e schijf een rode was. Dan hebt ge bij uw while 700 iteraties. Bij uw for maar 500, want ik start in de helft (500 is het centrum, 250-750). Mijn som is niet 500 maar 498. Dus moet ik niet meer verderzoeken.

Uitbreidbaar naar n-op-een-rij in een rij van m schijven waarbij n < m.

Maar toegegeven, het is zeker niet de moeite waard om te implementeren. Er zullen zeker situaties zijn waar de while dan rapper is. Dit voorbeeld is natuurlijk ook extreem gekozen.

Ik zou wel nooit de kracht van wiskunde in algoritmes onderschatten. We zien genoeg voorbeelden in onze lessen (Google's zoekalgoritmes en zo).

Laten we zeggen dat voor 4 op een rij te spelen het verschil in performance tussen O

en O(log n) wel te verwaarlozen valt.
Wat me wel opvalt bij al jullie oefeningen hier is een serieus gebrek aan oo programmatie. Ik snap niet waarom 'beginners' (no offence) het altijd zo moeilijk vinden, terwijl het juist de meest logische oplossing is.
bv: maak een klasse 'Disc' waaraan je gewon kan vragen: disc.isRed() of disc.isYellow() heel het kleur probleem ineens opgelost en iedereen die de code leest, begrijpt meteen waarover het gaat.
Dit kan je verder trekken naar bv: (en dit is enkel voor het model)
class Game: setup methoden om uw spel te starten
class Disc met bv: xPos, yPos, color
class Playingfield: (uw echt speelveld)
intern kan je dan bv het speelveld voorstellen door een 2 dimensionale array. (Werkt uitermate handig in dit geval).
daarin kan je wat methodes schrijven als in:

Code:

private Disc getDiscLeftOf(Disc anotherDisc) {
 if (hasDiscToTheLeft(anotherDisc) {
 return discArray[anotherDisc.posX - 1][anotherDisc.poxY];
} else {
 return null;
}
}
private Disc getDiscRightOf(Disc anotherDisc);
private Disc getDiscBelowOf(Disc anotherDisc);
private Disc getDiscDiagonalDownLeftOf(Disc anotherDisc);
private Disc getDiscDiagonalDownRightOf(Disc anotherDisc);
private Disc getDiscDiagonalUpLeftOf(Disc anotherDisc);
private Disc getDiscDiagonalUpRightOf(Disc anotherDisc);

private boolean hasDiscToTheLeft(Disc anotherDisc) {
 return anotherDisc.posX > 0;
}

Is zeker geen perfecte code, maar wel super leesbaar en hopelijk snap je mijn bedoeling wat.

MilM · 15 mei 2007

Ice zei:
Laten we zeggen dat voor 4 op een rij te spelen het verschil in performance tussen O en O(log n) wel te verwaarlozen valt.

Bij een gesorteerde rij kun je de helft van een rij gaan schrappen omdat je al weet dat de éne helft niet het getal zal bevatten.

Dat is hier niet het geval.
Het is dus wel degelijk O

in functie van de lengte van de rij.
In zijn voorbeeld komt dus geen logfunctie voor

En de complexiteit van de orginele vraag (4 op een rij tov het speelveld) is dus voor alle duidelijkheid O(1) (constant dus)

loopylama · 15 mei 2007

via boomstructuur

MilM · 15 mei 2007

loopylama zei:
via boomstructuur

En hoe ga gij uw velden invullen in uw boomstructuur ?
Een boomstructuur is trouwens enkel log wanneer je één van de kinderen kunt schrappen.

Zie wederom het voorbeeld van een gesorteerde rij.
Je bekijtk het middelste getal en afhankelijk daarvan schrap je de linker of rechterhelft van de rij.
Met een boom is dat ook zo.
Afhankelijk daarvan schrap je de linker of rechterdeelboom.

Maar je moet dan wel eerst een voorwaarde hebben om een deelboom te schrappen ...

loopylama · 15 mei 2007

MilM zei:
En hoe ga gij uw velden invullen in uw boomstructuur ?
Een boomstructuur is trouwens enkel log wanneer je één van de kinderen kunt schrappen.

zelfde algoritme ongeveer van pathfinding algoritme

volledig recursief wel dus niet simpel

MilM · 15 mei 2007

loopylama zei:
zelfde algoritme ongeveer van pathfinding algoritme

volledig recursief wel dus niet simpel

Bedoel je nu om log tijd te verkrijgen of gewoon als oplossing ?
Want als oplossing is da toch wel heel overdreven om voor zo iets kleins een boomstructuur te gaan maken.

Zoals ik al aangaf, het zijn maximum 15 checks.

loopylama · 15 mei 2007

MilM zei:
Bedoel je nu om log tijd te verkrijgen of gewoon als oplossing ?
Want als oplossing is da toch wel heel overdreven om voor zo iets kleins een boomstructuur te gaan maken.

het is de snelste oplossing

MilM · 15 mei 2007

loopylama zei:
het is de snelste oplossing

Als zoekalgoritme vertrekkend van de laatste schijf of wanneer je tussenoplossingen bijhoudt ? (bv rijen van 3)

En ik heb al uitgelegd dat de complexiteit constant is.
Beter kan niet ...

loopylama · 15 mei 2007

MilM zei:
Als zoekalgoritme vertrekkend van de laatste schijf of wanneer je tussenoplossingen bijhoudt ? (bv rijen van 3)

En ik heb al uitgelegd dat de complexiteit constant is.
Beter kan niet ...

ja ik geef toe dat het complex is

je hoeft alleen de vorige node bij te houden

je start het zoeken op 1 je bekijkt vakken errond indien zelfde kleur zoek je terug de vakken errond uitgezonderd dat waar je vandaan komt... enzovoort

tot je op de vierde stap komt en weer 1 van dezelfde kleur vindt. dan heb je vier op een rij

Archief - [PROG]Java code voor vier op een rij te detecteren

michael87

Legacy Member

MilM

Legacy Member

Timmos

Legacy Member

Timmos

Legacy Member

MilM

Legacy Member

Timmos

Legacy Member

MilM

Legacy Member

MilM

Legacy Member

Timmos

Legacy Member

[BAT] Hydra

Legacy Member

MilM

Legacy Member

Ice

Legacy Member

MilM

Legacy Member

loopylama

Legacy Member

MilM

Legacy Member

loopylama

Legacy Member

MilM

Legacy Member

loopylama

Legacy Member

MilM

Legacy Member

loopylama

Legacy Member