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, PointerToIOV 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 result < sum < 1000 and
 193          currentAttempt.digits[0] != 0 and
 194          currentAttempt.digits[3] >= 1 Then {
 195       result:
 196         = sum;
 197       firstNumber:
 198         = max(currentAttempt.digits[0] * 100 + currentAttempt.digits[1] * 10 +
 199                   currentAttempt.digits[2],
 200               currentAttempt.digits[3] * 100 + currentAttempt.digits[4] * 10 +
 201                   currentAttempt.digits[5]);
 202       secondNumber:
 203         = min(currentAttempt.digits[0] * 100 + currentAttempt.digits[1] * 10 +
 204                   currentAttempt.digits[2],
 205               currentAttempt.digits[3] * 100 + currentAttempt.digits[4] * 10 +
 206                   currentAttempt.digits[5]);
 207       }
 208       EndIf
 209     }
 210     Else {
 211       Integer16 newDigit : = 0;
 212       While newDigit <= 9 Loop {
 213         If NDEBUG = 0 Then {
 214           Character debugOutput[64] : = {0};
 215           strcat(AddressOf(debugOutput[0]),
 216                  "DEBUG: Let's check whether we can add the digit: ");
 217           convertIntegerToString(AddressOf(debugOutput[0]) +
 218                                      strlen(AddressOf(debugOutput[0])),
 219                                  newDigit);
 220           strcat(AddressOf(debugOutput[0]), "\n");
 221           printString(AddressOf(debugOutput[0]));
 222         }
 223         EndIf;
 224         Integer32 howManyInCurrentAttempt
 225             : = count(AddressOf(currentAttempt), newDigit);
 226         Integer32 howManyInTheTask : = count(AddressOf(digitsInTask), newDigit);
 227         If NDEBUG = 0 Then {
 228           Character debugOutput[128] : = {0};
 229           PointerToCharacter debugOutput : = AddressOf(debugOutput[0]);
 230           strcat(debugOutput, "DEBUG: There are ");
 231           convertIntegerToString(debugOutput + strlen(debugOutput),
 232                                  howManyInCurrentAttempt);
 233           strcat(debugOutput, " in the current attempt, and there are ");
 234           convertIntegerToString(debugOutput + strlen(debugOutput),
 235                                  howManyInTheTask);
 236           strcat(debugOutput, " in the task.\n");
 237           printString(debugOutput);
 238         }
 239         EndIf;
 240         If howManyInCurrentAttempt < howManyInTheTask Then {
 241           If NDEBUG = 0 Then {
 242             printString("DEBUG: It loooks as though we can.\n");
 243           }
 244           EndIf;
 245           topOfTheStack += 1;
 246           stackOfAttempts[topOfTheStack] : = currentAttempt;
 247           stackOfAttempts[topOfTheStack].length += 1;
 248           stackOfAttempts[topOfTheStack].digits[currentAttempt.length]
 249               : = newDigit;
 250         }
 251         EndIf;
 252         newDigit += 1;
 253       }
 254       EndWhile;
 255     }
 256     EndIf;
 257   }
 258   EndWhile;
 259   If result = -1 Then { strcpy(AddressOf(output[0]), "Bilbo"); }
 260   Else {
 261     convertIntegerToString(AddressOf(output[0]), result);
 262     strcat(AddressOf(output[0]), "=");
 263     convertIntegerToString(AddressOf(output[0]) + strlen(AddressOf(output[0])),
 264                            firstNumber);
 265     strcat(AddressOf(output[0]), "+");
 266     convertIntegerToString(AddressOf(output[0]) + strlen(AddressOf(output[0])),
 267                            secondNumber);
 268   }
 269   EndIf;
 270   Return AddressOf(output[0]);
 271 }
 272 EndFunction;
 273 
 274 Function main() Which Returns Nothing Does {
 275   printString("The result for the first test sample: ");
 276   printString(solveFor(5, 3, 6, 2, 6, 8));
 277   printString("\n");
 278   printString("The result for the second test sample: ");
 279   printString(solveFor(4, 2, 0, 2, 0, 1));
 280   printString("\n");
 281   printString("The result for the third test sample: ");
 282   printString(solveFor(9, 8, 7, 7, 6, 8));
 283   printString("\n");
 284   /*
 285   So, this outputs:
 286   ```
 287 The result for the first test sample: 993=668+325
 288 The result for the second test sample: 630=420+210
 289 The result for the third test sample: Bilbo
 290   ```
 291   */
 292 }
 293 EndFunction;
 294 
 295 asm(R"WebAssembly(
 296 	(export
 297 		"_start"
 298 		(func $main)
 299 	)
 300 )WebAssembly");
 301