3
\$\begingroup\$

So glad I found this cool site. Wanted to try sharing a coding challenge a friend gave me, an interview question. Usually it is written in java, but you can use whatever language you want, just have fun!

Challenge: write efficiently and securely a program that creates an array of n threads that communicate with each other, where each thread, for simplicity, represents a number between 1,...,100. Oh, and it has to be randomly initialized.

Here comes the fun part: each thread looks at its neighbours(i-1,i+1) and:

  • If its number is smaller than the number of both of his neighbours(i-1,i+1), it increments itself.

  • If its number is larger than the numbers of both of his neighbours, it decrements itself.

  • If its number is equal or between the numbers of its neighbours, it keeps the number the same.

So far not fun, right? So let's also make it a circular array! (the first element in the array and the last element in the array are neighbours) the tricky parts are: each thread should not change its number before its neighbors finished checking it.

The program performs m rounds of checks.

Input: For program logic, you can take the input from the user, or define it, doesn't matter.

Output: first line should print the starting state of the array. Second line should print all of the numbers in the array after each thread did one check. Third line should print the numbers in all of the array after each thread did a second test(second round) and so on.

Might be quite tricky in the beginning, but have fun with it! The winner will be the one who can write the shortest code, and in case of a tie, cool algorithmic tricks or functional utilization of the java language will be awarded extra points!


First post here, will try to post more cool stuff for you to enjoy! Really like this site.

I posted it a while ago, but forgot my credentials while being abroad so I couldn't log in to the site and fix the previous post. Hoping that this one is according to the standards of the site and more than that, I really hope you'll enjoy this cool coding gamexercise.

Good luck to all and most importantly - enjoy!

As kevin well-said: Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.

\$\endgroup\$

closed as unclear what you're asking by xnor, O.O.Balance, Digital Trauma, mbomb007, Xcali May 2 at 21:55

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    \$\begingroup\$ Although a good challenge, I have the feeling this can be done without threads? All integers in the array check their neighbors, and increment/decrements/stay the same based on that, and continue doing so for m iterations. So if I understand correctly we get an input n (array-size) and m (amount of iterations)? \$\endgroup\$ – Kevin Cruijssen May 2 at 11:16
  • 1
    \$\begingroup\$ @Puzzle Well, not all languages have threads, hence the question. Also, if this is code-golf, doing it without threads would be shorter in Java as well. But after making an answer in 05AB1E I will try to make an answer in Java both with an without threads. :) \$\endgroup\$ – Kevin Cruijssen May 2 at 11:24
  • 1
    \$\begingroup\$ As for the random number, is it including or excluding 1 and 100? So is the range [1 ... 100], [2 ... 100], [1 ... 99], or [2 ... 99]? It states in between, which would mean [2, 99]. Or alternatively, are all four options allowed (and perhaps [0 ... 99] / [0 ... 100] as well? Just trying to save some bytes here, haha ;p \$\endgroup\$ – Kevin Cruijssen May 2 at 12:30
  • 3
    \$\begingroup\$ Please define efficiently and securely. \$\endgroup\$ – Adám May 2 at 12:38
  • 2
    \$\begingroup\$ So this is a challenge about iteratively updating a list of numbers? I'm confused what at all this has to do with threads. \$\endgroup\$ – xnor May 2 at 17:25
4
\$\begingroup\$

05AB1E, 35 bytes

FтLΩˆ}>µ¯©=´vy®N<N>‚èy.SDPiн+ë\}ˆ}¼

Takes n as first input, and m as second. Doesn't use any threads, since 05AB1E has none.

Try it online.

Explanation:

F    }               # Loop the (implicit) input `n` amount of times:
 тL                  #  Push a list in the range [1,100]
   Ω                 #  Pop and push a random value from this list
    ˆ                #  Pop and add it to the global array
>                    # Increase the second (implicit) input `m` by 1
 µ                   # Loop until the counter_variable is equal to that:
  ¯                  #  Push the global array
   ©                 #  Store it in the register (without popping)
    =                #  Print it with trailing newline (without popping)
     ´               #  And clear the global array
   v                 #  Loop over each item of the array that is still on the stack:
      N<             #   Get the index-1
        N>           #   And the index+1
          ‚          #   Pair them together
     ®     è         #   Index both into the previous array we stored in the register
                     #   (NOTE: 05AB1E has automatic wrap-around when indexing)
            y.S      #   Compare both of them to the current integer `y`
                     #   (-1 if `y` is larger; 1 if `y` is smaller; 0 if equal)
               D     #   Duplicate this pair
                Pi   #   If the product is 1 (only true for [1,1] and [-1,-1]):
                  н  #    Only leave the first element of the duplicated pair
    y              + #    And add it to the current integer `y`
                 ë   #   Else:
                  \  #    Discard the duplicated pair, so `y` is at the top of the stack
                 }ˆ  #   After the if-else: add it to the global array
   }¼                #  After the inner loop: increase the counter_variable by 1
\$\endgroup\$
  • \$\begingroup\$ it's like cheating hehehe. is it okay if i limit it only to java or typical programming languages to give all people fair chance? \$\endgroup\$ – Puzzle May 2 at 15:39
  • 1
    \$\begingroup\$ @Puzzle Usually challenges are open to all language. Also, define 'typical'. :) But I'll probably get outgolfed anyway by someone programming in Jelly. ;p When I create challenges I usually also add the sentence: "Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language." It's never really about winning/losing a challenge, only about having fun doing the challenges. PS: I'm working on the Java multi-threading one, but I suck with threading, so will take a bit longer.. \$\endgroup\$ – Kevin Cruijssen May 2 at 15:53
  • \$\begingroup\$ adding your sentence to my post! \$\endgroup\$ – Puzzle May 2 at 16:01
3
\$\begingroup\$

Java 8, 229 bytes (lambda without threads)

n->m->{int a[]=new int[n],b[],i=n,t;for(;i-->0;)a[i]=(int)(Math.random()*100)+1;for(;m-->=0;a=b)for(System.out.println(java.util.Arrays.toString(a)),b=a.clone(),i=n;i-->0;)b[i]+=(t=a[(n+~i)%n]-a[i])*(a[-~i%n]-a[i])>0?t<0?-1:1:0;}

Try it online.

Java 8, 299 bytes (full program without threads)

interface Main{static void main(String[]A){int n=new Short(A[0]),m=new Short(A[1]),a[]=new int[n],b[],i=n,t;for(;i-->0;)a[i]=(int)(Math.random()*100)+1;for(;m-->=0;a=b)for(System.out.println(java.util.Arrays.toString(a)),b=a.clone(),i=n;i-->0;)b[i]+=(t=a[(n+~i)%n]-a[i])*(a[-~i%n]-a[i])>0?t<0?-1:1:0;}}

Try it online.

Explanation:

n->m->{              // Method with two integer parameters and no return-type
  int a[]=new int[n],//  Create an array of size `n`
      b[],           //  Temp array, uninitialized
      i=n,           //  Index-integer, starting at `n`
      t;             //  Temp integer, uninitialized
  for(;i-->0;)       //  Loop `i` in the range (`n`, 0]:
    a[i]=(int)(Math.random()*100)+1;
                     //   Fill the `i`'th item in the array with a random integer in 
                     //   the range [1, 100]
  for(;m-->=0;       //  Loop `m` times:
      a=b)           //    After every iteration: replace array `a` with `b`
    for(System.out.println(java.util.Arrays.toString(a)),
                     //   Print array `a` with trailing newline
        b=a.clone(), //   Create a copy of array `a` in `b`
        i=n;i-->0;)  //   Inner loop `i` in the range (`n`, 0]:
      b[i]+=         //    Increase the `i`'th item in array `b` by:
        (t=a[(n+~i)%n]-a[i])
                     //     Calculate a[i-1] minus a[i] (temporarily stored in `t`)
        *(a[-~i%n]-a[i])
                     //     Multiply it by a[i+1] minus a[i]
         >0?         //     If this is positive:
            t<0?     //      If `t` is negative:
             -1      //       Decrease b[i] by 1
            :        //      Else (`t` is positive):
             1       //       Increase b[i] by 1
        :            //     Else (a[i-1]-a[i] and a[i+1]-a[i] are pos/neg or neg/pos, 
                     //           or one of the two is 0)
         0;}         //      Leave b[i] the same by adding 0

Java 10, 569 537 bytes (full program with threads)

import java.util.concurrent.*;class M{C[]c;CyclicBarrier b;int n,m,i;public static void main(String[]a){new M().t(a);}void t(String[]a){m=new Short(a[1]);c=new C[n=new Short(a[0])];for(;i<n;)c[i]=new C(i++);b=new CyclicBarrier(n,()->{System.out.println(java.util.Arrays.toString(c));});for(var x:c)new Thread(x).start();}class C implements Runnable{int v=100,i,q,L,R,t;C(int I){i=I;v*=Math.random();v++;}public void run(){try{for(;q++<=m;R=c[-~i%n].v,t=v<L&v<R?1:v>L&v>R?-1:0,b.await(),v+=t)L=c[(n+~i)%n].v;}catch(Exception ex){}}public String toString(){return""+v;}}}

As mentioned earlier in a comment, without threads is much shorter..

Try it online (with class M is replaced with class Main, since it won't work on TIO if the class isn't called exactly Main..)

Explanation:

import java.util.concurrent.*; // Required import for CyclicBarrier
class M{                       // Class:
  C[]c;                        //  Array of our Runnable cells on class-level
  CyclicBarrier b;             //  A CyclicBarrier
  int n,                       //  Size of the array
      m,                       //  Amount of cycles
      i;                       //  Index, implicitly starting at 0
  public static void main(String[]a){
                               //  Mandatory main method:
    new M()                    //   Create an instance of this class
        .t(a);}                //   And call the non-static method below:
  void t(String[]a){           //  Non-static method for the actual program:
    m=new Short(a[1]);         //   Fill the amount of cycles `m` with the second argument
    c=new C[n=new Short(a[0])  //   Fill the size `n` with the first argument
             ];                //   Create the array of that size
    for(;i<n;)                 //   Loop over all cells in the array:
      c[i]=new C(i++);         //    And create a new instance for each cell
    b=new CyclicBarrier(n,     //   Create the CyclicBarrier of size `n`
       ()->{                   //    Which will do the following before every cycle:
          var p="";            //     Create a String to print, starting empty
          for(var x:c)         //     Loop over the cells
            p+=x.v+" ";        //      Append the cell's value and a space to the String
          System.out.println(p);});
                               //     Print the String with trailing newline
    for(var x:c)               //   Loop over the cells again:
      new Thread(x)            //    Create a new thread for this Runnable cell
        .start();}             //    And start the thread
  class C                      //  Inner class for the cells
      implements Runnable{     //  which implements the Runnable interface
    int v=100,                 //   The value of this cell, starting at 100
        i,                     //   The index of this cell
        q,                     //   A counter for the cycles
        L,R,                   //   Values of the left and right neighbors
        t;                     //   Incremental integer
    C(int I){                  //  In the constructor of the cell:
      i=I;                     //   Set the index `i` on the given index
      v*=Math.random();v++;}   //   And set `v` to a random integer in the range [1,100]
    public void run(){         //  Override the Runnable run method:
      try{                     //   Mandatory try-catch for InterruptedException
        for(;q++<=m;           //    Loop `m+1` times using the cycle-counter `q`
            ;                  //      After every iteration:
             R=c[-~i%n].v,     //       Get the value in the right-neighboring cell
             t=v<L&v<R?        //       If this cell's value is smaller than both neighbors:
                1              //        Set the incremental to 1
               :v>L&v>R?       //       Else-if this cell's value is larger than both neighbors:
                -1             //        Set the incremental to -1
               :               //       Else (value is smaller than or equal to one neighboring cell
                               //             and larger than or equal to the other neighboring cell):
                0,             //        Set the incremental to 0
             b.await(),        //       Wait until all cells in this BarrierCycle are done
             v+=t)             //       And only then increase/decrease the value with the incremental
          L=c[(n+~i)%n].v;     //     Get the value in the left-neighboring cell
      }catch(Exception ex){}}}}//   Mandatory try-catch for InterruptedException
\$\endgroup\$
  • 1
    \$\begingroup\$ Here's a pastebin for my half-assed thread attempt lol. I haven't done much with synchronous threading-- only async (this isn't a functional solution). I'm really interested to see this done for synchronous threads using the actual Runnable interface. \$\endgroup\$ – Magic Octopus Urn May 2 at 17:35
  • 1
    \$\begingroup\$ @MagicOctopusUrn Isn't your TIO missing something? You initialize boolean m=false;, but you never make it true? Also, although you're using threads, it isn't really async nor waiting on one-another. You're using the Threads only as a wrapper-class for the value and index and have a Thread.sleep.. :S As for your last sentence, I was working on something with a Runnable interface, but got stuck. Will try again today based on the two answers given. \$\endgroup\$ – Kevin Cruijssen May 3 at 7:29
  • 1
    \$\begingroup\$ @MagicOctopusUrn Added an async program with multi-threading, utilizing BarrierCycle in combination with a Runnable class and Thread. \$\endgroup\$ – Kevin Cruijssen May 3 at 9:37
  • 1
    \$\begingroup\$ Never seen a CyclicBarrier before, that's awesome. As for the sleep statements, I was just seeing if crap even worked; it wasn't intended to be a solution haha. Mostly brain vomit. \$\endgroup\$ – Magic Octopus Urn May 3 at 17:30
  • 1
    \$\begingroup\$ @MagicOctopusUrn I've also never seen CyclicBarrier before, but I came across this SO question which has a boolean matrix and wants to insert Jogn Conway's life simulator with multi-threading, where the cells also wait until everyone is done before actually updating, just like this challenge. And the accepted answer used the CyclicBarrier. I still had to get some help when I was stuck, since I'm a noob when it comes to multithreading, but it works. :) \$\endgroup\$ – Kevin Cruijssen May 3 at 17:43
2
\$\begingroup\$

Javascript, 209 bytes

for(a=[],l=n=prompt();n;)a[--n]=(M=Math).floor(M.random()*100+1);for(console.log(a),m=prompt();--m;)b=a.slice(),b.forEach((e,i)=>b[i]+=e<M.min(x=b[(i-1+l)%l],y=b[(i+1)%l])?1:e>M.min(x,y)?-1:0),console.log(a=b)

This program, upon running, will prompt the user twice. First for n(number of threads, but instead made with arrays), second for m(number of checks).

\$\endgroup\$
2
\$\begingroup\$

C# (Visual C# Interactive Compiler), 198 bytes

n=>m=>{int[]z=new int[n],g;int i=n,a;for(var k=new Random();i>0;z[--i]=k.Next(1,101));for(;m-->0;z=g){g=z.ToArray();i=0;for(Print(z);i<n;g[i]+=(a=z[(n+~i)%n]-z[i])*(z[-~i%n]-z[i++])>0?a<0?-1:1:0);}}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ If you actually wanted to use threads you could have used the following: Parallel.For(0,n,j=>{g[j]+=(a=z[(n+~j)%n]-z[j])*(z[-~j%n]-z[j])>0?a<0?-1:1:0;}); \$\endgroup\$ – Johan du Toit May 3 at 7:32

Not the answer you're looking for? Browse other questions tagged or ask your own question.