A blog on Computer Science, Security, Programming, and more...

HeapSpray Blog » Programming » View Post

09
May
2015

Permutation Solution to an Exercise

Just posting this to link as a solution to: https://blog.svpino.com/2015/05/08/solution-to-problem-5-and-some-other-thoughts-about-this-type-of-questions

Permutations are a fun alternative to recursion. The three possibilities +, -, and (concatenation) in the 8 places between the numbers can easily be represented as an 8-digit number in base 3. Representing that number as an array and incrementing it one by one allows you to iterate through all possibilities without recursion, taking each individual digit in the array as binary function between i+1 and i+2. No allocations!

#include <stdio.h>

void inc_field(int field){

field++;

for (int i = 7; i >= 0; i--){
switch (field[i]){
case 4:
case 3:
field[i] = (field[i])%3;
if (i-1 >= 0) field[i-1]++;
break;

default:
break;
}
}
}

int field_get_item(int field, int i){

int left = i+1;

if (i > 7)
return left;

switch(field[i]){
case 0:
while (i < 8 && field[i] == 0){
left = left*10 + (i+2);
i++;
}
break;
default:
break;
}

return left;
}

int field_next_pos(int field, int i){

if (field[i] != 0)
return i;

while (i < 8 && field[i] == 0)
i++;

return i;
}

void print_field(int field){

for (int i = 0; i < 8; i++){
putchar(i + '0' + 1);
if (field[i] == 1)
putchar('+');
if (field[i] == 2)
putchar('-');
}

putchar('9');
}

int main(int argc, char **argv){

// 0 = nothing, 1 = +, 2 = -
int field = {0};

// 3 values per position, 1,2,3,4,5,6,7,8,9 == 8 positions, 3^8 == 6501
for (int i = 0; i < 6561; i++){

int hold = 0;
int j = 0;

hold = field_get_item(field, j);

while (j < 8){

int n = field_next_pos(field, j);
int right = field_get_item(field, n+1);

switch(field[n]){
case 1:
hold += right;
break;
case 2:
hold -= right;
break;
}

j = field_next_pos(field, n);
if (j == n) j++;
}

if (hold == 100){
print_field(field);
printf(" == %d\n", hold);
}

inc_field(field);
}

return 0;
}

Result:

123+45-67+8-9 == 100
123+4-5+67-89 == 100
123-45-67+89 == 100
123-4-5-6-7+8-9 == 100
12+3+4+5-6-7+89 == 100
12+3-4+5+67+8+9 == 100
12-3-4+5-6+7+89 == 100
1+23-4+56+7+8+9 == 100
1+23-4+5+6+78-9 == 100
1+2+34-5+67-8+9 == 100
1+2+3-4+5+6+78+9 == 100
• Name and Email fields are optional
• Your email will not be public, only the administrator can see it
• You are rate limited to one comment for every 10 minutes