Hi,
I’m not 100% sure the code below is completely correct, but I don’t care as much about the exact output as I do about you learning the concepts involved. I’ve pasted below what I told the marker yesterday.
I agree with one of you who said of my example code for counting the 3-colourings of Nova Scotia, “my eyes are on fire, it’s so ugly”. That many nested for-loops is kind of stomach-turning. (Incidentally, though, you know you can set most editors to display tabs as however many spaces you want?) As I explained in the notes, though, I’m not going to distributed a general solution because I want to be able to use this exercise if Dal has me teach this course again.
Cheers,
Travis
PS Someone pointed out a couple of typos in my code. After those are fixed (done now, in the code below), the number returned shrinks by a factor of about 3 (from about 26 trillion to about 9 trillion). I told the marker to accept anything within a factor of 1000 of (what we think is) the right answer — that is, in the billions or trillions, up to a few quadrillion.
=====
Hi Simran,
I’ve attached the code I wrote, which takes a few seconds to run and says 26730015178752. I’m not 100% sure that’s correct — I wrote the code late at night — but it sounds plausible. I don’t really care if people get exactly the same answer, as long as their answer makes sense and it seems they understood what they were doing.
For the rubric, how about this?
5: obviously knows what they’re doing, code at least as likely to be correct as mine, could be distributed as a model solution
4: no obvious errors in the code, semi-plausible output but clearly wrong after a minute’s thought (e.g., only in the millions)
3: some errors in the code obvious in 30 seconds, or the output is clearly wrong
2: on the right track but some errors in the code obvious in 10 seconds
1: wrote something semi-coherent but clearly had no real idea what they were doing
0: complete gibberish
You can start marking right away. Even the people with extensions should submit by midnight tonight. It may take another few rounds of reminders for people to remember that groups upload the assignment only once (please check to see if you have duplicates from different group members, so you don’t accidentally mark the same thing twice) but all group members must upload something to receive a mark (so the ones who not submitting the assignment submit text files with the names and banner numbers of the group members, so you find their marks quickly).
Thanks again,
Travis
=====
#include
long long int countA();
long long int countB();
long long int countC();
long long int countD();
long long int countE();
long long int countF();
long long int A1, A2, A3, A4, A5, A6;
long long int B1, B2, B3, B4, B5, B6, B7, B8, B9, B10, B11, B12;
long long int C1, C2, C3, C4;
long long int D1, D2, D3, D4, D5, D6, D7;
long long int E1, E2, E3, E4, E5, E6, E7, E8, E9;
long long int F1, F2, F3, F4;
int main() {
long long int counter = 0, temp;
for (A5 = 0; A5 < 4; A5++) { for (B6 = 0; B6 < 4; B6++) { for (B7 = 0; B7 < 4; B7++) { for (B9 = 0; B9 < 4; B9++) { for (D5 = 0; D5 < 4; D5++) { if (D5 != A5 && D5 != B7) { for (D6 = 0; D6 < 4; D6++) { if (D6 != B7 && D6 != D5) { for (E3 = 0; E3 < 4; E3++) { for (E5 = 0; E5 < 4; E5++) { counter += countA() * countB() * countC() * countD() * countE() * countF(); } } } } } } } } } } printf("The number of 4-colourings is %lli.\n", counter); return(0); } long long int countA() { long long int counterA = 0; for (A1 = 0; A1 < 4; A1++) { if (A1 != A5) { for (A2 = 0; A2 < 4; A2++) { if (A2 != A1 && A2 != A5 && A2 != B7) { for (A3 = 0; A3 < 4; A3++) { if (A3 != A2 && A3 != A5 && A3 != B7 && A3 != D5) { for (A4 = 0; A4 < 4; A4++) { if (A4 != A2) { for (A6 = 0; A6 < 4; A6++) { if (A6 != A1 && A6 != A2 && A6 != A4) { counterA++; } } } } } } } } } } return(counterA); } long long int countB() { long long int counterB = 0; for (B1 = 0; B1 < 4; B1++) { if (B1 != B7 && B1 != D6) { for (B2 = 0; B2 < 4; B2++) { if (B2 != B1 && B2 != B9) { for (B3 = 0; B3 < 4; B3++) { if (B3 != B1 && B3 != B2 && B3 != B7 && B3 != B9) { for (B4 = 0; B4 < 4; B4++) { if (B4 != B6) { for (B5 = 0; B5 < 4; B5++) { if (B5 != B6) { for (B8 = 0; B8 < 4; B8++) { if (B8 != B2 && B8 != B4 && B8 != B5 && B8 != B6) { for (B10 = 0; B10 < 4; B10 ++) { if (B10 != B2 && B10 != B4 && B10 != B8) { for (B11 = 0; B11 < 4; B11++) { if (B11 != B1 && B11 != B2 && B11 != B10 && B11 != D6) { for (B12 = 0; B12 < 4; B12++) { if (B12 != B4 && B12 != B6 && B12 != B10) { counterB++; } } } } } } } } } } } } } } } } } } return(counterB); } long long int countC() { long long int counterC = 0; for (C1 = 0; C1 < 4; C1++) { for (C2 = 0; C2 < 4; C2++) { if (C2 != B9) { for (C3 = 0; C3 < 4; C3++) { if (C3 != C1 && C3 != C2) { for (C4 = 0; C4 < 4; C4++) { if (C4 != C1 && C4 != C2 && C4 != C3) { counterC++; } } } } } } } return(counterC); } long long int countD() { long long int counterD = 0; for (D1 = 0; D1 < 4; D1++) { for (D2 = 0; D2 < 4; D2++) { if (D2 != D1 && D2 != E5) { for (D3 = 0; D3 < 4; D3++) { if (D3 != D1 && D3 != D5 && D3 != D6) { for (D4 = 0; D4 < 4; D4++) { if (D4 != D1 && D4 != D2 && D4 != D3 && D4 != D6) { for (D7 = 0; D7 < 4; D7++) { if (D7 != A5 && D7 != D1 && D7 != D3 && D7 != D5) { counterD++; } } } } } } } } } return(counterD); } long long int countE() { long long int counterE = 0; for (E1 = 0; E1 < 4; E1++) { if (E1 != B6) { for (E2 = 0; E2 < 4; E2++) { if (E2 != E1) { for (E4 = 0; E4 < 4; E4++) { if (E4 != E3) { for (E6 = 0; E6 < 4; E6++) { if (E6 != E1 && E6 != E2 && E6 != E5) { for (E7 = 0; E7 < 4; E7++) { if (E7 != E2 && E7 != E4 && E7 != E5 && E7 != E6) { for (E8 = 0; E8 < 4; E8++) { if (E8 != E4 && E8 != E5 && E8 != E7) { for (E9 = 0; E9 < 4; E9++) { if (E9 != E2 && E9 != E3 && E9 != E4 && E9 != E7) { counterE++; } } } } } } } } } } } } } } return(counterE); } long long int countF() { long long int counterF = 0; for (F1 = 0; F1 < 4; F1++) { for (F2 = 0; F2 < 4; F2++) { if (F2 != A5 && F2 != F1) { for (F3 = 0; F3 < 4; F3++) { if (F3 != F1 && F3 != F2) { for (F4 = 0; F4 < 4; F4++) { if (F4 != E3 && F4 != F2 && F4 != F3) { counterF++; } } } } } } } return(counterF); }