2022 day11

6 files changed, 643 insertions, 0 deletions

diff --git a/2022/day11/input1.txt b/2022/day11/input1.txt
new file mode 100644
index 0000000..30e09e5
--- /dev/null
+++ b/2022/day11/input1.txt
@@ -0,0 +1,27 @@
+Monkey 0:
+  Starting items: 79, 98
+  Operation: new = old * 19
+  Test: divisible by 23
+    If true: throw to monkey 2
+    If false: throw to monkey 3
+
+Monkey 1:
+  Starting items: 54, 65, 75, 74
+  Operation: new = old + 6
+  Test: divisible by 19
+    If true: throw to monkey 2
+    If false: throw to monkey 0
+
+Monkey 2:
+  Starting items: 79, 60, 97
+  Operation: new = old * old
+  Test: divisible by 13
+    If true: throw to monkey 1
+    If false: throw to monkey 3
+
+Monkey 3:
+  Starting items: 74
+  Operation: new = old + 3
+  Test: divisible by 17
+    If true: throw to monkey 0
+    If false: throw to monkey 1
diff --git a/2022/day11/input2.txt b/2022/day11/input2.txt
new file mode 100644
index 0000000..d87f089
--- /dev/null
+++ b/2022/day11/input2.txt
@@ -0,0 +1,55 @@
+Monkey 0:
+  Starting items: 99, 67, 92, 61, 83, 64, 98
+  Operation: new = old * 17
+  Test: divisible by 3
+    If true: throw to monkey 4
+    If false: throw to monkey 2
+
+Monkey 1:
+  Starting items: 78, 74, 88, 89, 50
+  Operation: new = old * 11
+  Test: divisible by 5
+    If true: throw to monkey 3
+    If false: throw to monkey 5
+
+Monkey 2:
+  Starting items: 98, 91
+  Operation: new = old + 4
+  Test: divisible by 2
+    If true: throw to monkey 6
+    If false: throw to monkey 4
+
+Monkey 3:
+  Starting items: 59, 72, 94, 91, 79, 88, 94, 51
+  Operation: new = old * old
+  Test: divisible by 13
+    If true: throw to monkey 0
+    If false: throw to monkey 5
+
+Monkey 4:
+  Starting items: 95, 72, 78
+  Operation: new = old + 7
+  Test: divisible by 11
+    If true: throw to monkey 7
+    If false: throw to monkey 6
+
+Monkey 5:
+  Starting items: 76
+  Operation: new = old + 8
+  Test: divisible by 17
+    If true: throw to monkey 0
+    If false: throw to monkey 2
+
+Monkey 6:
+  Starting items: 69, 60, 53, 89, 71, 88
+  Operation: new = old + 5
+  Test: divisible by 19
+    If true: throw to monkey 7
+    If false: throw to monkey 1
+
+Monkey 7:
+  Starting items: 72, 54, 63, 80
+  Operation: new = old + 3
+  Test: divisible by 7
+    If true: throw to monkey 1
+    If false: throw to monkey 3
diff --git a/2022/day11/main.c b/2022/day11/main.c
new file mode 100644
index 0000000..52ec2e2
--- /dev/null
+++ b/2022/day11/main.c
@@ -0,0 +1,157 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+typedef struct Monkey_ Monkey;
+
+typedef struct Monkey_ {
+    long long item[64];
+    int items, is_multiply, opertant_is_old, operant, test, test_true, test_false, inspections;
+} Monkey;
+
+Monkey* newMonkey() 
+{
+    char *line = NULL;
+    size_t size;
+    size_t len;
+    Monkey *monkey = malloc(sizeof(Monkey));
+    monkey->inspections = 0;
+    // items
+    len = getline(&line, &size, stdin);
+
+    char *begin = line+18;
+    char *token = NULL;
+    for (int j = 0; (token = strsep(&begin, ",")); j++) 
+    {
+        // printf("%u: %s\n", j, token);
+        monkey->item[j] = atoi(token);
+        monkey->items = j+1;
+    }
+
+    // operation
+    len = getline(&line, &size, stdin);
+    monkey->is_multiply = line[23] == '*';
+    monkey->opertant_is_old = line[25] == 'o';
+    if (!monkey->opertant_is_old)
+    {
+        monkey->operant = atoi(line+25);
+    }
+
+    // test
+    len = getline(&line, &size, stdin);
+    monkey->test = atoi(line+21);
+
+    // test true
+    len = getline(&line, &size, stdin);
+    monkey->test_true = atoi(line+29);
+
+    // test true
+    len = getline(&line, &size, stdin);
+    monkey->test_false = atoi(line+30);
+
+    len = getline(&line, &size, stdin);
+    return monkey;
+}
+
+void inspect(Monkey *monkey, Monkey *monkeys[])
+{
+    monkey->inspections += monkey->items;
+    for (int i = 0; i < monkey->items; i++)
+    {
+        // set operant
+        int operant = monkey->operant;
+        if (monkey->opertant_is_old)
+            operant = monkey->item[i];
+
+        // set operation
+        if (monkey->is_multiply) 
+        {
+            monkey->item[i] *= operant;
+        } else {
+            monkey->item[i] += operant;
+        }
+
+        monkey->item[i] /= 3;
+
+        // throw item based on test
+        int throw = monkey->test_true;
+        if (monkey->item[i] % monkey->test != 0)
+        {
+            throw = monkey->test_false;
+        }
+
+        monkeys[throw]->item[monkeys[throw]->items] = monkey->item[i];
+        monkeys[throw]->items++;
+    }
+    monkey->items = 0;
+}
+
+int main()
+{
+
+    int monkeys = 0;
+    Monkey *monkey[10] = { };
+
+    char *line = NULL;
+    size_t size;
+    size_t len;
+    int active1 = 0, active2 = 0;
+
+    while ((len = getline(&line, &size, stdin)) != -1)
+    {
+        // create monkeys
+        Monkey *new = newMonkey();
+        monkey[monkeys] = new;
+        monkeys++;
+        
+        // print monkey attributes
+        printf("Items:");
+        for (int i = 0; i < new->items; i++)
+        {
+            printf("%lldd ", new->item[i]);
+        }
+        printf("\n %d %d %d %d %d %d\n\n",
+            new->is_multiply,
+            new->opertant_is_old,
+            new->operant,
+            new->test,
+            new->test_true,
+            new->test_false
+                );
+    }
+
+    for (int i = 0; i < 20; i++)
+    {
+        // do inspection
+        for (int ii = 0; ii < monkeys; ii++)
+        {
+            inspect(monkey[ii], monkey);
+        }
+        
+        // output rounds
+        printf("Round %d\n", i);
+        for (int ii = 0; ii < monkeys; ii++)
+        {
+            printf("Monkey %d: ", ii);
+            for (int iii = 0; iii < monkey[ii]->items; iii++)
+            {
+                printf("%lld ", monkey[ii]->item[iii]);
+            }
+            printf("\n");
+        }
+    }
+    
+    // get two most active monkeys
+    for (int i = 0; i < monkeys; i++)
+    {
+        if (monkey[i]->inspections > active1) 
+        {
+            active2 = active1;
+            active1 = monkey[i]->inspections;
+        }
+        printf("Monkey %d inspected items %d times. \n", i, monkey[i]->inspections);
+    }
+
+    printf("Monkey biz: \n%d\n", active1 * active2);
+}
+
diff --git a/2022/day11/main2.c b/2022/day11/main2.c
new file mode 100644
index 0000000..86d471e
--- /dev/null
+++ b/2022/day11/main2.c
@@ -0,0 +1,165 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdint.h>
+#include <gmp.h>
+
+typedef struct Monkey_ Monkey;
+
+typedef struct Monkey_ {
+    mpz_t item[64];
+    int items, is_multiply, opertant_is_old, operant, test, test_true, test_false, inspections;
+} Monkey;
+
+Monkey* newMonkey() 
+{
+    char *line = NULL;
+    size_t size;
+    size_t len;
+    Monkey *monkey = malloc(sizeof(Monkey));
+    monkey->inspections = 0;
+    // items
+    len = getline(&line, &size, stdin);
+
+    char *begin = line+18;
+    char *token = NULL;
+    for (int j = 0; (token = strsep(&begin, ",")); j++) 
+    {
+        // printf("%u: %s\n", j, token);
+        // monkey->item[j] = atoi(token);
+        mpz_init_set_str(monkey->item[j], token, 10);
+        monkey->items = j+1;
+    }
+
+    // operation
+    len = getline(&line, &size, stdin);
+    monkey->is_multiply = line[23] == '*';
+    monkey->opertant_is_old = line[25] == 'o';
+    if (!monkey->opertant_is_old)
+    {
+        monkey->operant = atoi(line+25);
+    }
+
+    // test
+    len = getline(&line, &size, stdin);
+    monkey->test = atoi(line+21);
+
+    // test true
+    len = getline(&line, &size, stdin);
+    monkey->test_true = atoi(line+29);
+
+    // test true
+    len = getline(&line, &size, stdin);
+    monkey->test_false = atoi(line+30);
+
+    len = getline(&line, &size, stdin);
+    return monkey;
+}
+
+void inspect(Monkey *monkey, Monkey *monkeys[])
+{
+    monkey->inspections += monkey->items;
+    for (int i = 0; i < monkey->items; i++)
+    {
+        // set operant
+        mpz_t operant; //= monkey->operant;
+        mpz_init_set_si(operant, monkey->operant);
+        if (monkey->opertant_is_old)
+            mpz_init_set(operant, monkey->item[i]);
+            // operant = monkey->item[i];
+
+        // set operation
+        if (monkey->is_multiply) 
+        {
+            // monkey->item[i] *= operant;
+            mpz_mul(monkey->item[i], monkey->item[i], operant);
+        } else {
+            // monkey->item[i] += operant;
+            mpz_add(monkey->item[i], monkey->item[i], operant);
+        }
+
+        // monkey->item[i] /= 3;
+
+        // throw item based on test
+        int throw = monkey->test_true;
+        if (!mpz_divisible_ui_p(monkey->item[i], monkey->test))
+        {
+            throw = monkey->test_false;
+        }
+
+        // monkeys[throw]->item[monkeys[throw]->items] = monkey->item[i];
+        mpz_set(monkeys[throw]->item[monkeys[throw]->items], monkey->item[i]);
+        monkeys[throw]->items++;
+    }
+    monkey->items = 0;
+}
+
+int main()
+{
+
+    int monkeys = 0;
+    Monkey *monkey[10] = { };
+
+    char *line = NULL;
+    size_t size;
+    size_t len;
+    long long active1 = 0, active2 = 0;
+
+    while ((len = getline(&line, &size, stdin)) != -1)
+    {
+        // create monkeys
+        Monkey *new = newMonkey();
+        monkey[monkeys] = new;
+        monkeys++;
+        
+        // print monkey attributes
+        printf("Items:");
+        for (int i = 0; i < new->items; i++)
+        {
+            printf("%lud ", new->item[i]);
+        }
+        printf("\n %d %d %d %d %d %d\n\n",
+            new->is_multiply,
+            new->opertant_is_old,
+            new->operant,
+            new->test,
+            new->test_true,
+            new->test_false
+                );
+    }
+
+    for (int i = 0; i < 10000; i++)
+    {
+        // do inspection
+        for (int ii = 0; ii < monkeys; ii++)
+        {
+            inspect(monkey[ii], monkey);
+        }
+        
+        // output rounds
+        printf("Round %d\n", i);
+        // for (int ii = 0; ii < monkeys; ii++)
+        // {
+        //     printf("Monkey %d: ", ii);
+        //     for (int iii = 0; iii < monkey[ii]->items; iii++)
+        //     {
+        //         printf("%lu ", monkey[ii]->item[iii]);
+        //     }
+        //     printf("\n");
+        // }
+    }
+    
+    // get two most active monkeys
+    for (int i = 0; i < monkeys; i++)
+    {
+        if (monkey[i]->inspections > active1) 
+        {
+            active2 = active1;
+            active1 = monkey[i]->inspections;
+        }
+        printf("Monkey %d inspected items %d times. \n", i, monkey[i]->inspections);
+    }
+
+    printf("Monkey biz: \n%lld\n", active1 * active2);
+}
+
diff --git a/2022/day11/main3.c b/2022/day11/main3.c
new file mode 100644
index 0000000..631cfdf
--- /dev/null
+++ b/2022/day11/main3.c
@@ -0,0 +1,214 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdint.h>
+
+typedef struct Monkey_ Monkey;
+
+typedef struct Monkey_ {
+    __uint128_t item[64];
+    __uint128_t items, is_multiply, opertant_is_old, operant, test, test_true, test_false, inspections;
+} Monkey;
+
+Monkey* newMonkey() 
+{
+    char *line = NULL;
+    size_t size;
+    size_t len;
+    Monkey *monkey = malloc(sizeof(Monkey));
+    monkey->inspections = 0;
+    // items
+    len = getline(&line, &size, stdin);
+
+    char *begin = line+18;
+    char *token = NULL;
+    for (int j = 0; (token = strsep(&begin, ",")); j++) 
+    {
+        // printf("%u: %s\n", j, token);
+        monkey->item[j] = atoi(token);
+        monkey->items = j+1;
+    }
+
+    // operation
+    len = getline(&line, &size, stdin);
+    monkey->is_multiply = line[23] == '*';
+    monkey->opertant_is_old = line[25] == 'o';
+    if (!monkey->opertant_is_old)
+    {
+        monkey->operant = atoi(line+25);
+    }
+
+    // test
+    len = getline(&line, &size, stdin);
+    monkey->test = atoi(line+21);
+
+    // test true
+    len = getline(&line, &size, stdin);
+    monkey->test_true = atoi(line+29);
+
+    // test true
+    len = getline(&line, &size, stdin);
+    monkey->test_false = atoi(line+30);
+
+    len = getline(&line, &size, stdin);
+    return monkey;
+}
+
+// int priminice(int n)
+// {
+//     int isPrime;
+//     int num = 1;
+//     for (int i = 2; i <= n; i++)
+//     {
+//         if(n % i == 0)
+//         {
+//             isPrime = 1;
+//             for (int j = 2; j <= i/2; j++)
+//             {
+//                 if(i % j == 0)
+//                 {
+//                     isPrime = 0;
+//                     break;
+//                 }
+//             } 
+//             if(isPrime == 1)
+//             {
+//                 // printf("\n %d is a Prime Factor ", i);
+//                 if ( num % i != 0 )
+//                 {
+//                     num *= i;
+//                 }
+//             }	          	
+//         }
+//     }
+//     return num;
+// }
+
+__uint128_t priminice(__uint128_t n)
+{
+    __uint128_t num = 1;
+    while (n%2 == 0){
+        // cout<<"2\t";
+        if ( num % 2 != 0)
+            num *= 2;
+        n = n/2;
+    }
+    for (int i = 3; i*i <= n; i = i+2){
+        while (n%i == 0){
+            // cout<<i<<"\t";
+            if (num % i != 0)
+                num *= i;
+            n = n/i;
+        }
+    }
+    if (n > 2)
+    {
+        if (num % n != 0)
+            num *= n;
+        // cout<<n<<"\t";
+    }
+    return num;
+}
+
+void inspect(Monkey *monkey, Monkey *monkeys[])
+{
+    monkey->inspections += monkey->items;
+    for (int i = 0; i < monkey->items; i++)
+    {
+        // set operant
+        __uint128_t operant = monkey->operant;
+        if (monkey->opertant_is_old)
+            operant = monkey->item[i];
+
+            // set operation
+        if (monkey->is_multiply )
+        {
+            monkey->item[i] *= operant;
+        } else {
+            monkey->item[i] += operant;
+        }
+
+        // monkey->item[i] /= 3;
+
+        // throw item based on test
+        int throw = monkey->test_true;
+        if (monkey->item[i] % monkey->test != 0)
+        {
+            throw = monkey->test_false;
+        }
+
+        monkeys[throw]->item[monkeys[throw]->items] = priminice(monkey->item[i]);
+        monkeys[throw]->items++;
+    }
+    monkey->items = 0;
+}
+
+int main(int argc, char *argv[])
+{
+
+    int monkeys = 0;
+    Monkey *monkey[10] = { };
+
+    char *line = NULL;
+    size_t size;
+    size_t len;
+    __uint128_t active1 = 0, active2 = 0;
+
+    while ((len = getline(&line, &size, stdin)) != -1)
+    {
+        // create monkeys
+        Monkey *new = newMonkey();
+        monkey[monkeys] = new;
+        monkeys++;
+        
+        // print monkey attributes
+        printf("Items:");
+        for (int i = 0; i < new->items; i++)
+        {
+            printf("%lud ", new->item[i]);
+        }
+        printf("\n %d %d %d %d %d %d\n\n",
+            new->is_multiply,
+            new->opertant_is_old,
+            new->operant,
+            new->test,
+            new->test_true,
+            new->test_false
+                );
+    }
+
+    for (int i = 0; i < atoi(argv[1]); i++)
+    {
+        // do inspection
+        for (int ii = 0; ii < monkeys; ii++)
+        {
+            inspect(monkey[ii], monkey);
+        }
+        
+        // output rounds
+        printf("Round %d\n", i);
+        for (int ii = 0; ii < monkeys; ii++)
+        {
+            printf("Monkey %d: ", ii);
+            for (int iii = 0; iii < monkey[ii]->items; iii++)
+            {
+                printf("%lu ", monkey[ii]->item[iii]);
+            }
+            printf("\n");
+        }
+    }
+    
+    // get two most active monkeys
+    for (int i = 0; i < monkeys; i++)
+    {
+        if (monkey[i]->inspections > active1) 
+        {
+            active2 = active1;
+            active1 = monkey[i]->inspections;
+        }
+        printf("Monkey %d inspected items %d times. \n", i, monkey[i]->inspections);
+    }
+
+    printf("Monkey biz: \n%lu %lu %lu\n", active1, active2, active1 * active2);
+}
+
diff --git a/2022/day11/test.c b/2022/day11/test.c
new file mode 100644
index 0000000..fe9a076
--- /dev/null
+++ b/2022/day11/test.c
@@ -0,0 +1,25 @@
+#include <stdio.h>
+int main()
+{
+    int n;
+    int num = 1;
+    printf("Enter the number you want: ");
+    scanf("%d", &n);
+    for(int i=2; i*i<=n; i++)
+    {
+        while(n%i==0)//find all the occurrences of a prime factor
+        {
+            printf("%d\n",i);
+            if (num % i != 0)
+                num *= i;
+            n/=i;
+        }
+    }
+    if(n!=1)//if the number was originally a prime
+    {
+        printf("%d",n);
+        num *= n;
+    }
+    printf("new %d\n", num);
+    return 0;
+}