NØTTER ("4 int", og flere!)

[anders02]

Jeg har dessverre glemt alt jeg kan om C++, har ikke C++-kompilator installert og vet ikke hvor C++-boken min er. Kan derfor ikke hjelpe deg med det som evt. måtte være C++-spesifikt.

 

Hva er pokeGrid og checkGrid? Har du laget noe kode her som du kan poste og som jeg kan se på? Er det du prøver å kode basert på min løsning eller på en algoritme du har funnet et annet sted?

[Frysning]

Bruker definerte funksjoner, det er de jeg vil skrive.

PokeGrid, kan være å random bare endre en tilfeldige verdi/klikke på en tilfeldig verdi.

CheckGrid er bare noe for å teste om en av de inneholder 0, altså alle er ikke tent enda.

De er ikke skrevet, alt jeg har laget er arrayen, en initfunksjonen samt en CheckGrid funksjon.

 

Jeg står egentlig litt på bar bakke, men ja, tar imot all hjelp på å løse selve problemet.

Det er det samme hvilket språk du poster kode i, som nevnt jeg har lest mye og kan litt av alt.

 

Så det jeg er ute etter, er vel bare psudokode på hvordan jeg kan poke/endre/trykke på lysene per loop.

[anders02]

Da skal jeg se om jeg i løpet av kvelden kan lage to metoder til deg i Java, en som sjekker om du har vunnet (checkGrid) og en som kjøres når man klikker på en knapp. Den sistnevnte tar inn koordinatene en knappen.

 

Disse metodene vil da greit kunne brukes til alle de tre løsningene jeg foreslo på problemet.

[Frysning]

Knall, det haster ikke altså.

Takk for at du tar deg tid.

Edit:

Oh, klarer å trykke meg frem til den nå iallefall.

Endret 27. juni 2007 av Frysning

[anders02]

Koden er som følger:

 

public class ALights {

private static int[][] t = new int[5][5];

 

public static void init() {

for (int i = 0; i < 5; i++) {

for (int j = 0; j < 5; j++) {

t[j] = 0;

}

}

}

 

public static boolean checkGrid() {

for (int i = 0; i < 5; i++) {

for (int j = 0; j < 5; j++) {

if (t[j] == 0) {

return false;

}

}

}

 

return true;

}

 

public static void pokeGrid(int x, int y) {

t[x][y] = 1 - t[x][y];

 

try {

t[x][y-1] = 1 - t[x][y-1];

} catch (Exception e) { }

 

try {

t[x-1][y] = 1 - t[x-1][y];

} catch (Exception e) { }

 

try {

t[x][y+1] = 1 - t[x][y+1];

} catch (Exception e) { }

 

try {

t[x+1][y] = 1 - t[x+1][y];

} catch (Exception e) { }

}

 

public static void printGrid() {

for (int i = 0; i < 5; i++) {

for (int j = 0; j < 5; j++) {

System.out.print(t[j] + " ");

}

System.out.println("");

}

}

 

public static void main(String[] args) {

init();

pokeGrid(0, 0);

printGrid();

}

}

 

Når jeg prøver å bruke CODE-taggen eller SKJUL-taggen får jeg bare følgende feilmelding:

Noen filer mangler. Hvis du ville se en tråd, kan den ha blitt slettet eller flyttet. Gå tilbake og prøv igjen.

 

Derfor ligger koden som den gjør her...

 

Hjelper denne koden deg noe?

[Frysning]

Jepp, den hjelper.

Skal skrive ferdig greien min nå, fri imorgen så har natten.

Hadde vært gøy å laget to programmer, en med 100% random og en som bruker din teknikk. Så se på tidsforskjellene.

 

Hvis du velger de to første lysene til å starte med, løser algoritmen den med en gang.

Burde iallefall det.

Endret 27. juni 2007 av Frysning

[anders02]

I tillegg kan du lage en som bruker bruteforce. Mener å huske at den brukte et par timer på en datamaskin som var middels bra for 5 år siden.

 

En random vil ikke ta like lang tid hver gang, og i teorien kan den bruke uendelig lang tid på en kjøring. Du vet heller ikke om denne metoden vil finne alle løsninger.

 

Du må gjerne poste kode og kjøretider hvis du blir ferdig. Gi beskjed hvis jeg skal skrive flere Java-metoder til deg.

 

Hvis du velger de to første lysene til å starte med, løser algoritmen den med en gang.

Burde iallefall det.

8958079[/snapback]

 

Hva mener du?

[Frysning]

Hvis du først velge lys 1 og 2.

Altså de to lysene oppe til venstre, så går videre og alltid klikker på de under mørke-ruter får løser du den.

 

Skal bli skøy å teste litt iallefall.

Endret 27. juni 2007 av Frysning

[anders02]

Ja, det har du rett i. Jeg begynte alltid med knapp 2, 3 og 5, det løser også problemet.

 

Gi beskjed når du har funnet ut hvor mange løsninger det er totalt på problemet.

[anders02]

Du har forhåpentligvis merket at dersom du klikker et partall antall ganger på den samme knappen så er det det samme som å ikke har trykket på knappen i det hele tatt. Ett oddetall antall ganger tilsvarer ett klikk.

 

Det kan da være greit å lage en tabell som holder oversikt over om en knapp er trykket eller ikke:

private static int[][] clicked = new int[5][5];

 

I tillegg kan man endre pokeGrid til å oppdatere clicked så man holder styr på om en knapp er trykket eller ei:

clicked[x][y] = 1 - clicked[x][y];

 

Da er det enkelt å lage metoden som klikker på tilfeldige knapper og sjekker svaret mellom hver knapp:

public static void randomForce() {

while (!checkGrid()) {

pokeGrid((int)(Math.random() * 5), (int)(Math.random() * 5));

}

}

 

Når den metoden har kjørt skriver du ut clicked-tabellen for å se én av løsningene på problemet. På min maskin tok det rundt et minutt å kjøre denne.

[Frysning]

Har skrevet klassen for "grid", med noen member-functions.

Men ikke implementert selve algoritmen enda, det kommer.

(Blitt bitt av Diablo 2, så har kasta bort litt for mye tid.)

 

Men hvordan finner man egentlig ALLE mulige løsninger?

Din teknikk/algoritme er jo en fremgangs måte, kan det finnes andre som gir flere løsninger?

[anders02]

Min algoritme finner garantert alle mulige løsninger. Årsaken til det er at den prøver å finne en løsning ut fra alle mulige utgangssituasjoner (altså alle 32 muligheter man kan ha i den øverste raden).

 

Bruteforce finner også alle løsninger.

 

Ettersom du ikke vet hvor mange løsninger det finnes totalt vil du ikke være garantert at randommetoden i forrige post finner alle løsninger.

 

På tide at du poster noe kode?

 

Jeg er heldig, jeg vet hvor mange løsninger det er totalt, og jeg vet hvordan jeg enkelt skal finne alle.

[Frysning]

Du skal få se koden når den er klar, jeg skal faktisk lære noe av dette.

Vil gjøre det skikkelig, btw.

Måten du løser den på, gjelder jo på alle 4 siden av griddet? Så da kan jo egentlig antall løsninger via en side slik som gjort her ganges med 4 for å få totalt antall løsninger?

[anders02]

Det stemmer. Når du har funnet én løsning har du funnet fire, dersom ikke løsningene er symmetriske.

 

Jeg har laget ferdig en bruteforce-metode også, og tidtakning av kjøretid. Nå mangler det bare å implementere algoritmen for å løse det hele raskt.

 

Har også kodet ferdig en løsning på problemet hentet fra rekursjonskapitlet, hvis du begynner på den oppgaven etter hvert.

 

Er forresten klar for en oppgave selv snart, har du eller noen andre noe på lager?

[teflonpanne]

Rekursjon:

#include <stdio.h>

int f_aux(int x, int a, int b)
{
 if (x == 0)
   return a;
 else return f_aux(x - 1, a + b, a);
}

int f(int x)
{
 f_aux(x, 1, 0);
}
 
int main()
{
 printf("%d\n",f(1000));
}

i haskell kan man lage en uendelig liste:

let f = 1 : 2 : zipWith (+) f (tail f) in take 1000 f

 

En ny nøtt kan være å finne hvor mange måter man kan veksle en 50-lapp på eller lage en brainfuck interpreter

 

edit: får ikke skjul-blokken til å funke, sier den mangler filer, hva er galt?

Endret 30. juni 2007 av teflonpanne

[anders02]

Jeg løste rekursjonsoppgaven uten rekursjon:

 

public static long array(int i) {
 long[] array = new long[i];
 array[0] = 1;
 array[1] = 2;

 for (int j = 2; j < i; j++) {
   array[j] = array[j-1] + array[j-2];
 }

 return array[i-1];
}

 

Følgende (med rekursjon) er mest logisk, men håpløst tregt:

public static long recursion(int i) {
 if (i == 1) {
   return 1;
 } else if (i == 2) {
   return 2;
 } else {
   return recursion(i-1) + recursion(i-2);
 }
}

 

I femtilapp-oppgaven antar jeg at bruteforce blir for tregt, eller?

 

Brainfuck-interpreter laget jeg for en liten stund siden i Java. Jeg har lekt med tanken på å lage et utviklingsmiljø, med mulighet for debugging, og live oppdatering av minne for hvert steg, men det har foreløpig bare blitt med tanken.

[anders02]

Jeg kommer til 867 hvis vi tar med valørene 0.5, 1, 5, 10, 20 og 50. Kan det stemme?

 

Og bruteforce var så absolutt ikke for tregt.

[teflonpanne]

866 skal det være..

Bedre å bruke backtracking enn bruteforce

 

edit, grunnen til at du fikk 867 er jo selvfølgelig at du tar med 50, det gjorde ikke jeg

Endret 30. juni 2007 av teflonpanne

[anders02]

Backtracking tror jeg ikke at jeg har hørt om. Kan du poste koden?

 

Etter min mening burde du valgt et større beløp enn 50 så jeg hadde skjønt at bruteforce ikke var måten du ville vi skulle løse problemet på, siden min kode brukte 23 ms og derfor ligger godt innenfor det man vanligvis gidder å vente på at et program skal kjøre ferdig.

[teflonpanne]

Backtracking er nesten bruteforce. Hvis man f.eks begynner med 20-kroner, så finner man ut at når man kommer til den tredje 20-kroningen så blir beløpet over 50 kroner, så da "backtracker" du tilbake til to 20-kroner og prøver med en tier i stedet.

 

Har bare haskellkode

Prelude> let sumTo set 0 = [[]]; sumTo set n = [i : xs | i <- set, n-i>=0, xs <- sumTo (filter (<= i) set) (n-i)] in length $ sumTo [20, 10, 5, 1, 0.5] 50

866