19
\$\begingroup\$

Intro

Consider a grid of the characters f A\/ such as

f  f  f  
      A  
   A / \ 
\ /     A
    A \/ 
   /     
 \/         

where:

  • f represents a faucet that pours a stream of water downward
  • A bifurcates the stream of water above so exactly half goes left and exactly half goes right
  • \ shifts the stream of water above to the right by one unit
  • / shifts the stream of water above to the left by one unit
  • the combinations \/ creates a trough with infinite capacity that collects the water streams above it
  • [space] is empty space than the water can move through

From this we can imagine the path the water (*) would take as it comes out of the faucets and falls either into the troughs or out of the grid area:

f  f  f    <-- first second and third faucets
*  * *A* 
* *A*/ \*
\*/ *  *A  <-- a '*' is not drawn to the right of this A because it would be out of the 9×7 bounds
 * *A*\/   <-- upper trough
 **/ *   
 \/  *     <-- lower trough

Assuming the 3 faucets output the same amount of water one at a time we can see that

  • All of the first faucet's water goes to the lower trough.
  • One half of the second faucet's water goes to the lower trough and the other half is split between the lower trough and falling off the grid.
  • One quarter of the third faucet's water goes to the lower trough, one quarter falls off the bottom of the grid, one quarter goes into the upper trough, and one quarter falls off the grid to the right.

From this we can tell that (1 + 3/4 + 1/4 + 1/4) / 3 = 75% of the water is caught by the troughs and (1/4 + 1/4 + 1/4) / 3 = 25% falls off the grid.

Challenges

You may complete any or all of these challenges relating to this ASCII water flow setup. They are all code-golf, the shortest answer for each challenge is the winner. The accepted answer will be the person who completes the most challenges, with total code length as tie-breaker.

Challenge 1
Write a program that outputs the fraction of water that flows into troughs for a given grid. The output of the example above would simply be 0.75.

Challenge 2
Write a program that, given a grid, draws the *'s in the places water flows as I've done above. You should not overwrite anything besides space characters and the grid should not change size. So for something like

 f
/A

nothing needs to be done since, although water does flow on either side of the A, it can't be drawn to the left without removing the / and it can't be drawn to the right without making the 2×2 grid bigger.

Challenge 3 (Updated)
Write a program that takes in two non-negative integers, the total T and the amount to keep K (T >= K). Generate and draw a grid with exactly one f such that when that faucet pours out T units of water, exactly K will flow into troughs. If it is impossible to do this in a finite grid for a particular (T, K) pair then output 'Impossible'.

Clarifications (apply to all challenges)

  • Input can be via stdin, or a file, or even a function call on the string representation of the grid. Just make it obvious how to run different inputs.
  • Output must go to stdout.
  • \A and A/ and AA are also troughs as you'd expect.
  • A w by h grid will always be a well formatted rectangle of w*h characters not counting newlines. There will be no missing trailing spaces and no occurrences of *.
  • The grid dimensions can be as small as 1×1 and arbitrarily large. (Arbitrarily large within reason, int.maxValue or the like is an acceptable limit. Same goes for T and K.)
  • A stream above an f flows right through it.
  • The faucets can be anywhere, not just on the top row.
  • A always divides the amount of water poured on it exactly in half.

Note: Things like /A and // are perfectly valid. The water does freely flow between the characters (though for challenge 2 there's not enough room to draw it).

So, in the setup

ff

/A

The left f stream pours down, hits the / and shifts left. The right f stream pours down, hits the A, half goes right and half goes left between the A and the /.

e.g.

 ff
 **
*/A*
** *
** *
\$\endgroup\$
  • 3
    \$\begingroup\$ +1 Nice challenge. As for challenge 3, the grid at top would not be a valid answer because it has 3 fs \$\endgroup\$ – edc65 Jul 16 '14 at 7:31
  • \$\begingroup\$ @edc65 Ah, good catch! \$\endgroup\$ – Calvin's Hobbies Jul 16 '14 at 7:34
  • 2
    \$\begingroup\$ Very very similar: codegolf.stackexchange.com/questions/26059/… \$\endgroup\$ – Howard Jul 16 '14 at 8:18
  • 2
    \$\begingroup\$ For the second challenge, you need to specify how to handle input like /A if water falls onto the A. For all challenges, it would be good to clarify whether \A is a trough. For the third challenge, should 3 units falling on an A be assumed to split 1.5 / 1.5 (so the input is really a single rational number) or is it 2 / 1, in which case which side receives the 2? \$\endgroup\$ – Peter Taylor Jul 16 '14 at 9:37
  • 1
    \$\begingroup\$ @PeterTaylor Thanks. I've clarified those points. I guess T and K could be floats but I'm keeping them integers for simplicity. (But if T=3 does hit an A then both sides do get 1.5. It's up to the coder to make sure float precision is not an issue.) \$\endgroup\$ – Calvin's Hobbies Jul 16 '14 at 10:03
3
\$\begingroup\$

All Challenges C# 690bytes (416bytes + 274bytes)

Challenges 1&2 C# 579 446 416bytes

This is a complete program which should do Challenges 1 & 2, just about. It reads lines of input from stdin until it receives an empty line. It prints out the result for Challenge 2, and then the result for Challenge 1. Uses the .NET decimal class to hopefully avoid any rounding errors.

using C=System.Console;class P{static void Main(){decimal u,t=0,f=0;string c,z="";for(decimal[]n=null,o;(c=C.ReadLine())!="";z+='\n'){int s=c.Length,i=s,e;o=n;n=new decimal[s];for(o=o??n;i-->0;n[i]+=(e&2)*u/2){e=c[i]%13;u=o[i]/(e<1?2:1);if(e%8<1)if(i>0)if(c[i-1]%7<3)t+=u;else n[i-1]+=u;if(e<2)if(i<s-1)if(c[i+1]%2>0)t+=u;else n[i+1]+=u;if(e>9){u++;f++;}}for(;++i<s;)z+=c[i]<33&n[i]>0?'*':c[i];}C.WriteLine(z+t/f);}}

Less golfed:

using C=System.Console;
class P
{
    static void Main()
    {
        decimal u,t=0,f=0;
        string c,z="";

        for(decimal[]n=null,o;(c=C.ReadLine())!="";z+='\n')
        {
            int s=c.Length,i=s,e;
            o=n;
            n=new decimal[s];
            for(o=o??n;i-->0;n[i]+=(e&2)*u/2)
            {
                e=c[i]%13;
                u=o[i]/(e<1?2:1);

                if(e%8<1)
                    if(i>0)
                        if(c[i-1]%7<3)t+=u;
                        else n[i-1]+=u;
                if(e<2)
                    if(i<s-1)
                        if(c[i+1]%2>0)t+=u;
                        else n[i+1]+=u;
                if(e>9)
                {
                    u++;
                    f++;
                }
            }
            for(;++i<s;)
                z+=c[i]<33&n[i]>0?'*':c[i];
        }

        C.WriteLine(z+t/f);
    }
}

Test run (with a lack of trailing spaces which I promise are there):

f  f  f
      A
   A / \
\ /     A
    A \/
   /
 \/

f  f  f
*  * *A*
* *A*/ \*
\*/ *  *A
 * *A*\/
 **/ *
 \/  *
0.75

Challenge 3 C# 274bytes

This is a complete program which should complete Challenge 3. I a managed to save 6bytes by writing my own integer parser to read the input rather than Spliting a ReadLine and using long.Parse;

using C=System.Console;class P{static void Main(){long t=-1,f=t,k;for(;f<0;)for(f=t,t=0;(k=C.Read())>47;)t=t*10+k-48;var r="Impossible\n";for(k=t;k<t*f;)k*=2;if(f<1||(k/f)*f==k)for(r=" f \n";t>0&t<f;t-=(t/f)*f)r+=((t*=2)<f?" ":"A")+"A \n/ /\n";C.Write(r+(t<f?"":"AAA\n"));}}

Less golfed:

using C=System.Console;
class P
{
    static void Main()
    {
        long t=-1,f=t,k;
        for(;f<0;)
            for(f=t,t=0;(k=C.Read())>47;)
                t=t*10+k-48;

        var r="Impossible\n";
        for(k=t;k<t*f;)
            k*=2;
        if(f<1||(k/f)*f==k)
            for(r=" f \n";t>0&t<f;t-=(t/f)*f)
                r+=((t*=2)<f?" ":"A")+"A \n/ /\n";
        C.Write(r+(t<f?"":"AAA\n"));
    }
}

Test run (again with a lack of trailing spaces which I promise are there):

32 17
 f
AA
/ /
 A
/ /
 A
/ /
 A
/ /
AA
/ /
\$\endgroup\$
3
\$\begingroup\$

First of all, I have a question regarding the challenge. Since I do not have enough reputation to comment on the question, I'm writing it here:

  • What is the behavior of /A (water flowing on A), // (water flowing on the right side) and variations of this principle? Does the water flow to the first "free spot" on the side or does is flow "below" its neighbour?

Just a simple try, it can be waaaaay simplified (which I will do later by editing this post).

Edit: Second version, a little bit smaller. I went for a different approach: instead of looking for each cell to check what's comming from the top and sides, I start from the faucets and "flow" downwards with recursion.

Javascript, 226 bytes (Challenge 1)

function f(c){function h(b,a,d,e){b<c.length&&0<=a&&a<c[0].length&&("\\"==c[b][a]?"/"==e||"A"==e?g+=d:h(b,a+1,d,"\\"):"/"==c[b][a]?"\\"==e||"A"==e?g+=d:h(b,a-1,d,"/"):"A"==c[b][a]?"A"==e||"\\"==e||"/"==e?g+=d:(h(b,a-1,d/2,"A"),h(b,a+1,d/2,"A")):h(b+1,a,d,c[b][a]))}for(var g=0,m=0,k=0;k<c.length;k++)for(var l=0;l<c[k].length;l++)"f"==c[k][l]&&(h(k+1,l,1),m++);alert(g/m)};

Javascript, 204 bytes (Challenge 2)

function f(c){function e(b,a,d){b<c.length&&0<=a&&a<c[0].length&&("\\"==c[b][a]?"/"!=d&&"A"!=d&&e(b,a+1,"\\"):"/"==c[b][a]?"\\"!=d&&"A"!=d&&e(b,a-1,"/"):"A"==c[b][a]?"A"!=d&&"\\"!=d&&"/"!=d&&(e(b,a-1,"A"),e(b,a+1,"A")):(" "==c[b][a]&&(c[b][a]="*"),e(b+1,a,c[b][a])))}for(var g=0;g<c.length;g++)for(var h=0;h<c[g].length;h++)"f"==c[g][h]&&e(g+1,h)};

Javascript, 238 bytes (Challenge 1 + 2)

function f(c){function h(b,a,d,e){b<c.length&&0<=a&&a<c[0].length&&("\\"==c[b][a]?"/"==e||"A"==e?g+=d:h(b,a+1,d,"\\"):"/"==c[b][a]?"\\"==e||"A"==e?g+=d:h(b,a-1,d,"/"):"A"==c[b][a]?"A"==e||"\\"==e||"/"==e?g+=d:(h(b,a-1,d/2,"A"),h(b,a+1,d/2,"A")):(" "==c[b][a]&&(c[b][a]="*"),h(b+1,a,d,c[b][a])))}for(var g=0,m=0,k=0;k<c.length;k++)for(var l=0;l<c[k].length;l++)"f"==c[k][l]&&(h(k+1,l,1),m++);alert(g/m)};

How to use

Provide a two dimensionnal representation ofthe map. Here is the example provided in the question:

var input = [["f"," "," ","f"," "," ","f"," "," "],[" "," "," "," "," "," ","A"," "," "],[" "," "," ","A"," ","/"," ","\\"," "],["\\"," ","/"," "," "," "," "," ","A"],[" "," "," "," ","A"," ","\\","/"," "],[" "," "," ","/"," "," "," "," "," "],[" ","\\","/"," "," "," "," "," "," "]];
f(input);

Output

Challenge 1: It will simply create a dialog box (alert) with the result (0.75 for the example above).

Challenge 2: It will directly modify the map. Should I print it? If so, is console.log is accepted? as a valid output?

Challenge 1+2: Both of above combined, obviously...

\$\endgroup\$
  • \$\begingroup\$ The water keeps on flowing between the characters as if it is hugging the lines of the A or the slashes. I've clarified that in the question. \$\endgroup\$ – Calvin's Hobbies Jul 21 '14 at 14:07
  • \$\begingroup\$ The question states Output must go to stdout. \$\endgroup\$ – user80551 Jul 22 '14 at 18:44
  • \$\begingroup\$ You specified as input format that you haveyo give an array of one-character strings per row, but bear in mind you can index str[0] into strings. That would be an array of strings instead of an array of arrays of characters. \$\endgroup\$ – tomsmeding Jul 22 '14 at 18:56
  • 1
    \$\begingroup\$ user80551 Thanks, I don't know why it slipped out of my mind. I will update my code as soon as possible. @tomsmeding Yes, it works for my answer of the challenge 1. But for the challenge 2 I'm directly modifying the input and you cannot modify a character in a string using str[i], hence the use of an array of arrays. \$\endgroup\$ – refreshfr Jul 23 '14 at 8:17
2
\$\begingroup\$

Python 3, 186 bytes (Challenge 3)

I took the idea for the grid from VisualMelon's answer. The function should print a valid grid to stdout for arbitrarily large T and K, provided it is possible (finite size grid) of course.

from fractions import*
def c(T,K):
 p=print;g=gcd(T,K);K//=g;T//=g
 if T&(T-1):p('Impossible')
 else:
  p(' f ')
  while T-1:
   T//=2;p('A/'[K<T]+'A \n///')
   if K>=T:K-=T
  p('AAA'*K)

How to use

Call the c function with the total amount and amount to keep as arguments.

>>> c(24, 9)
 f 
/A 
///
AA 
///
AA 
///

>>> c(6, 2)
Impossible
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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