1 // This is my solution to the task Bilbo from Infokup 2013, the school-level
   2 // competition in informatics for grade 8.
   3 // https://informatika.azoo.hr/natjecanje/dobavi-dokument/458
   4 // Basically, you receive 6 digits as an input, and you have to arrange those
   5 // 6 digits into 2 3-digit numbers so that the sum of the two three-digit
   6 // numbers is as big as possible without exceeding 1000 and output that sum. If
   7 // that is not possible, you have to output the string "Bilbo".
   8 
   9 // First, a lot of boilerplate to target WASI...
  10 #target WASI
  11 
  12 Structure IOV Consists Of {
  13   PointerToCharacter iov_base;
  14   Integer32 iov_len;
  15 }
  16 EndStructure;
  17 
  18 Function
  19 fd_write(Integer32 file_descriptor, IOVPointer iovs, Integer32 iovs_len,
  20          PointerToInteger32 nwritten) Which Returns Integer32 Is External;
  21 
  22 Function strlen(PointerToCharacter str) Which Returns Integer32 Does {
  23   Integer32 size : = 0;
  24   While ValueAt(str + size) Loop { size += 1; }
  25   EndWhile;
  26   Return size;
  27 }
  28 EndFunction;
  29 
  30 Integer32 stdout : = 1;
  31 InstantiateStructure IOV iov;
  32 Integer32 dummy_integer : = 0;
  33 
  34 Function printString(PointerToCharacter string) Which Returns Nothing Does {
  35   iov.iov_base : = string;
  36   iov.iov_len : = strlen(string);
  37 dummy_integer:
  38   = fd_write(stdout, AddressOf(iov),
  39              1 /*Because we are printing only 1 string.*/,
  40              AddressOf(dummy_integer));
  41 }
  42 EndFunction;
  43 
  44 // Let's finally start solving the task...
  45 Structure ArrayOfDigits Consists Of {
  46   Integer16 length;
  47   Integer16 digits[6];
  48 }
  49 EndStructure;
  50 
  51 InstantiateStructure ArrayOfDigits digitsInTask;
  52 
  53 Function count(PointerToArrayOfDigits array,
  54                Integer16 digit) Which Returns Integer16 Does {
  55   Integer16 result : = 0, i : = 0;
  56   While i < array->length Loop {
  57     If array->digits[i] = digit Then { result += 1; }
  58     EndIf;
  59     i += 1;
  60   }
  61   EndWhile;
  62   Return result;
  63 }
  64 EndFunction;
  65 
  66 Function strcpy(PointerToCharacter dest,
  67                 PointerToCharacter src) Which Returns Nothing Does {
  68   While ValueAt(src) Loop {
  69     ValueAt(dest) : = ValueAt(src);
  70     dest += 1;
  71     src += 1;
  72   }
  73   EndWhile;
  74   ValueAt(dest) : = 0;
  75 }
  76 EndFunction;
  77 
  78 Function strcat(PointerToCharacter dest,
  79                 PointerToCharacter src) Which Returns Nothing Does {
  80   strcpy(dest + strlen(dest), src);
  81 }
  82 EndFunction;
  83 
  84 Function reverseString(PointerToCharacter string) Which Returns Nothing Does {
  85   PointerToCharacter pointerToLastCharacter : = string + strlen(string) - 1;
  86   While pointerToLastCharacter - string > 0 Loop {
  87     Character tmp : = ValueAt(string);
  88     ValueAt(string) : = ValueAt(pointerToLastCharacter);
  89     ValueAt(pointerToLastCharacter) : = tmp;
  90     string += 1;
  91     pointerToLastCharacter -= 1;
  92   }
  93   EndWhile;
  94 }
  95 EndFunction;
  96 
  97 Function convertIntegerToString(PointerToCharacter string,
  98                                 Integer32 number) Which Returns Nothing Does {
  99   Integer32 isNumberNegative : = 0;
 100   If number < 0 Then {
 101   number:
 102     = -number;
 103   isNumberNegative:
 104     = 1;
 105   }
 106   EndIf;
 107   Integer32 i : = 0;
 108   While number >= 10 Loop {
 109     ValueAt(string + i) : = '0' + mod(number, 10);
 110     number /= 10;
 111     i += 1;
 112   }
 113   EndWhile;
 114   ValueAt(string + i) : = '0' + number;
 115   i += 1;
 116   If isNumberNegative Then {
 117     ValueAt(string + i) : = '-';
 118     i += 1;
 119   }
 120   EndIf;
 121   ValueAt(string + i) : = 0;
 122   reverseString(string);
 123 }
 124 EndFunction;
 125 
 126 InstantiateStructure ArrayOfDigits stackOfAttempts[128];
 127 Integer32 topOfTheStack : = -1;
 128 
 129 Function max(Integer32 a, Integer32 b) Which Returns Integer32 Does {
 130   Return a > b ? a : b;
 131 }
 132 EndFunction;
 133 
 134 Function min(Integer32 a, Integer32 b) Which Returns Integer32 Does {
 135   Return a < b ? a : b;
 136 }
 137 EndFunction;
 138 
 139 Character output[16];
 140 
 141 Integer32 NDEBUG : = 1;
 142 
 143 Function solveFor(Integer16 a, Integer16 b, Integer16 c, Integer16 d,
 144                   Integer16 e,
 145                   Integer16 f) Which Returns PointerToCharacter Does {
 146   Integer16 initialArray[6] : = {a, b, c, d, e, f}, i : = 0;
 147   digitsInTask.length : = 6;
 148   While i < 6 Loop {
 149     digitsInTask.digits[i] : = initialArray[i];
 150     i += 1;
 151   }
 152   EndWhile;
 153   Integer32 result : = -1, firstNumber, secondNumber;
 154 topOfTheStack:
 155   = 0;
 156   stackOfAttempts[topOfTheStack].length : = 0;
 157   While topOfTheStack >= 0 Loop {
 158     InstantiateStructure ArrayOfDigits currentAttempt
 159         : = stackOfAttempts[topOfTheStack];
 160     If NDEBUG = 0 Then {
 161       Character debugOutput[64] : = {0};
 162       strcat(AddressOf(debugOutput[0]), "DEBUG: Trying the attempt: ");
 163       Character printingCurrentAttempt[7] : = {0, 0, 0, 0, 0, 0, 0};
 164       Integer16 counter : = 0;
 165       While counter < currentAttempt.length Loop {
 166         printingCurrentAttempt[counter]
 167             : = currentAttempt.digits[counter] + '0';
 168         counter += 1;
 169       }
 170       EndWhile;
 171       strcat(AddressOf(debugOutput[0]), AddressOf(printingCurrentAttempt[0]));
 172       strcat(AddressOf(debugOutput[0]), "    \n");
 173       printString(AddressOf(debugOutput[0]));
 174     }
 175     EndIf;
 176     topOfTheStack -= 1;
 177     If currentAttempt.length = 6 Then {
 178       Integer32 sum
 179           : = currentAttempt.digits[0] * 100 + currentAttempt.digits[1] * 10 +
 180               currentAttempt.digits[2] + currentAttempt.digits[3] * 100 +
 181               currentAttempt.digits[4] * 10 + currentAttempt.digits[5];
 182       If NDEBUG = 0 Then {
 183         Character debugOutput[64] : = {0};
 184         strcat(AddressOf(debugOutput[0]),
 185                "DEBUG: Found a potential solution with the sum: ");
 186         convertIntegerToString(
 187             AddressOf(debugOutput[0]) + strlen(AddressOf(debugOutput[0])), sum);
 188         strcat(AddressOf(debugOutput[0]), "\n");
 189         printString(AddressOf(debugOutput[0]));
 190       }
 191       EndIf;
 192       If sum<1000 and sum> result Then {
 193       result:
 194         = sum;
 195       firstNumber:
 196         = max(currentAttempt.digits[0] * 100 + currentAttempt.digits[1] * 10 +
 197                   currentAttempt.digits[2],
 198               currentAttempt.digits[3] * 100 + currentAttempt.digits[4] * 10 +
 199                   currentAttempt.digits[5]);
 200       secondNumber:
 201         = min(currentAttempt.digits[0] * 100 + currentAttempt.digits[1] * 10 +
 202                   currentAttempt.digits[2],
 203               currentAttempt.digits[3] * 100 + currentAttempt.digits[4] * 10 +
 204                   currentAttempt.digits[5]);
 205       }
 206       EndIf
 207     }
 208     Else {
 209       Integer16 newDigit : = 0;
 210       While newDigit <= 9 Loop {
 211         If NDEBUG = 0 Then {
 212           Character debugOutput[64] : = {0};
 213           strcat(AddressOf(debugOutput[0]),
 214                  "DEBUG: Let's check whether we can add the digit: ");
 215           convertIntegerToString(AddressOf(debugOutput[0]) +
 216                                      strlen(AddressOf(debugOutput[0])),
 217                                  newDigit);
 218           strcat(AddressOf(debugOutput[0]), "\n");
 219           printString(AddressOf(debugOutput[0]));
 220         }
 221         EndIf;
 222         Integer32 howManyInCurrentAttempt
 223             : = count(AddressOf(currentAttempt), newDigit);
 224         Integer32 howManyInTheTask : = count(AddressOf(digitsInTask), newDigit);
 225         If NDEBUG = 0 Then {
 226           Character debugOutput[128] : = {0};
 227           PointerToCharacter debugOutput : = AddressOf(debugOutput[0]);
 228           strcat(debugOutput, "DEBUG: There are ");
 229           convertIntegerToString(debugOutput + strlen(debugOutput),
 230                                  howManyInCurrentAttempt);
 231           strcat(debugOutput, " in the current attempt, and there are ");
 232           convertIntegerToString(debugOutput + strlen(debugOutput),
 233                                  howManyInTheTask);
 234           strcat(debugOutput, " in the task.\n");
 235           printString(debugOutput);
 236         }
 237         EndIf;
 238         If howManyInCurrentAttempt < howManyInTheTask Then {
 239           If NDEBUG = 0 Then {
 240             printString("DEBUG: It loooks as though we can.\n");
 241           }
 242           EndIf;
 243           topOfTheStack += 1;
 244           stackOfAttempts[topOfTheStack] : = currentAttempt;
 245           stackOfAttempts[topOfTheStack].length += 1;
 246           stackOfAttempts[topOfTheStack].digits[currentAttempt.length]
 247               : = newDigit;
 248         }
 249         EndIf;
 250         newDigit += 1;
 251       }
 252       EndWhile;
 253     }
 254     EndIf;
 255   }
 256   EndWhile;
 257   If result = -1 Then { strcpy(AddressOf(output[0]), "Bilbo"); }
 258   Else {
 259     convertIntegerToString(AddressOf(output[0]), result);
 260     strcat(AddressOf(output[0]), "=");
 261     convertIntegerToString(AddressOf(output[0]) + strlen(AddressOf(output[0])),
 262                            firstNumber);
 263     strcat(AddressOf(output[0]), "+");
 264     convertIntegerToString(AddressOf(output[0]) + strlen(AddressOf(output[0])),
 265                            secondNumber);
 266   }
 267   EndIf;
 268   Return AddressOf(output[0]);
 269 }
 270 EndFunction;
 271 
 272 Function main() Which Returns Nothing Does {
 273   printString("The result for the first test sample: ");
 274   printString(solveFor(5, 3, 6, 2, 6, 8));
 275   printString("\n");
 276   printString("The result for the second test sample: ");
 277   printString(solveFor(4, 2, 0, 2, 0, 1));
 278   printString("\n");
 279   printString("The result for the third test sample: ");
 280   printString(solveFor(9, 8, 7, 7, 6, 8));
 281   printString("\n");
 282 }
 283 EndFunction;
 284 
 285 asm("(export \"_start\" (func $main))");
 286