Do We Sink or Swim?

Question

The Problem

A doomsday scenario is described by three numbers on a single line, n, m, and p. Following that line are n lines with m values per line. Each value represents the total units of water each cell can hold.

The following p lines describe the weather for the next p days. 1 unit of rain falls on a single cell each day. If the amount of water in a cell exceeds the amount it can hold, that cell floods. If multiple adjacent cells are at full capacity, they are treated as one cell that share common neighbors (think Minesweeper when you click on a group of blanks).

• A single middle cell has 4 neighbors
• Two adjacent, full capacity middle cells are treated as one cell that has 6 neighbors
• A single corner cell has 2 neighbors
• A single wall cell has 3 neighbors

When a cell floods, a flood event occurs. All excess water is evenly distributed to its neighbors. If that causes one or more neighbors to flood, then another flood event occurs. This continues until the water has settled, or the city has completely flooded.

Example Input

7 5 3
3 2 3 4 5
2 2 0 3 4
1 1 2 3 3
4 1 2 2 2
4 1 1 2 2
4 4 1 2 2
4 4 2 2 2
0 0
1 2
4 3

• 0 0 means it rained on row 1, col 1
• 1 2 means it rained on row 2, col 3 (which can hold zero water and immediately floods!)

After p days of rain, if the city is completely flooded, output Sink. Otherwise, output Swim.

Example Output

Swim

Assumptions

• Input may be provided through stdin, read from "city.txt", or accepted as an argument. All three are allowed so as not to invalidate any answers already posted.
• Water capacities will be non-negative integers.

40+ teams of undergrad college students (from A&M, UT, LSU, Rice, Baylor, etc.) competing in a programming contest with a variety of languages available could not solve this problem in 5 hours. Because of that, I can't help but mention that there is a catch to this puzzle that makes the solution trivial. Shortest code still wins, because I am that confident that the shortest code will also solve the puzzle.

Answer 1

Golfscript, 37 30 characters

New and improved, thanks to PeterTaylor for tips:

~](\(@*\(@@<{+}*>"SwimSink"4/=

Explanation:

Code                     -                                            - Stack
~]                       - parse input into an array of integers      - []
(                        - pop first number and put on stack          - [] 7
\(                       - \ swaps top two, then pop first num again  - 7 [] 5
@                        - bring 3rd down from stack to front         - [] 5 7
*                        - mult. this is grid size                    - [] 35
\(@                      - bring next # out - the days of rain        - [] 3 35
@                        - bring array out                            - 3 35 []
<                        - take first 35 elements out of array.
                           this extracts just the capacities and 
                           consumes the rest                          - 3 []
{+}*                     - fold the array using plus - this sums the
                           entire thing                               - 3 86
<                        - greater-than comparison: 3 > 86?           - 0
"SwimSink"4/             - push a string and split it to groups of 4  - 0 ["Swim" "Sink"]

=                        - index into the array using the result of
                           the comparison. if rain > capacity, then
                           sink, else swim                            - "Swim"

Program then terminates, outputting the stack.

---

Old version + explanation:

[~](\(@*\(@{\(@\-}*\;0>"Sink""Swim"if

Same approach as Fors, just Golfscripted =). Can likely be made more efficient. Input is from stdin.

Explanation:

Code                     -                                            - Stack
[~]                      - parse input into an array of integers      - []
(                        - pop first number and put on stack          - [] 7
\(                       - \ swaps top two, then pop first num again  - 7 [] 5
@                        - bring 3rd down from stack to front         - [] 5 7
*                        - mult. this is grid size                    - [] 35
\(@                      - bring next # out - the days of rain        - [] 3 35
{                        - define a block which...
 \(@                     - brings next number out
 \-                      - swaps and subtracts 2nd down from top
}                                                                     - [] 3 35 {}
*                        - repeat that block 35 times. this ends up
                           pulling the capacities out one by one
                           and decrementing our number-of-days 
                           number by each one                         - [] -84 
\;                       - swap and kill the array to get rid of
                           unused input                               - -84
0>"Sink""Swim"if         - if the num > 0, evaluate to "Sink", 
                           otherwise to "Swim"                        - "Swim"

Program then outputs the stack, which is just the answer.

Answer 2

C: 100 96 95 characters

n,m;main(p){scanf("%d%d%d",&n,&m,&p);for(n*=m;n--;scanf("%d",&m))p-=m;puts(p>0?"Sink":"Swim");}

Five hours? Took me five minutes. :)

Aragaer, thank you for the simplifications! I did however rearrange the variable declarations and arguments to main, seeing as Clang throws an error if the second argument to main is of any other type than char **.

Answer 3

Python, 4 lines, 175 characters

import sys 
F=sys.stdin
n,m,p=[int(a) for a in F.readline().split()]
print("sink") if p > sum([sum(int(x) for x in F.readline().split()) for a in range(n)]) else print("swim")

Lol, I wonder if the 40+ teams ended up finding the catch... after working it out the hard way.

Answer 4

J (50 char) and K (40) double feature

Turns out, as usual, these two have the exact same structure in their solutions, so they're both here. K is a whole lot shorter, though, which is a pleasant surprise.

>Sink`Swim{~(]<[:+/[+/@".@$+1!:1@#1:)/0 2{".1!:1]1

Explanation:

• ".1!:1]1 - Read in the first line, and convert to integers.
• (...)/0 2{ - Take the items at index 0 and 2 (n and p respectively), and use them as the left and right arguments to the verb (...), respectively.
• +1!:1@#1: - Read in n+p lines.
• [+/@".@$ - Take ($) the first n rows ([), discarding the rest, and then convert to integers (".) and sum on each row (+/).
• ]<[:+/ - Add together the row sums, and then compare this value to the right argument, p. We produce true if p is less than the sum.
• >Sink`Swim{~ - Select Swim if the above comprasion resulted in true, or Sink if false.

Usage:

   >Sink`Swim{~(]<[:+/[+/@".@$+1!:1@#1:)/0 2{".1!:1]1
7 5 3
3 2 3 4 5
2 0 3 3 4
1 1 2 3 3
4 1 2 2 2
4 1 1 2 2
4 4 1 2 2
4 4 2 2 2
0 0
1 2
4 3
Swim

And now the K:

`Sink`Swim@{z<+//.:'x#0::'(x+z)#`}.. 0:`

Explained:

• . 0:` - Read in a line of input, and convert to an array of integers.
• {...}. - Use these three numbers n m p as the arguments x y z to this function.
• 0::'(x+z)#` - Create x+z copies of the input file handle `, and then read in a line for each of them (0::').
• .:'x# - Take the first x items, and convert each to a vector of numbers.
• z<+// - Sum the entire matrix together, and then test to see if it is greater than z.
• `Sink`Swim@ - Return Sink or Swim according to whether the test returned true.

Usage:

  `Sink`Swim@{z<+//.:'x#0::'(x+z)#`}.. 0:`
7 5 3
3 2 3 4 5
2 2 0 3 4
1 1 2 3 3
4 1 2 2 2
4 1 1 2 2
4 4 1 2 2
4 4 2 2 2
0 0
1 2
4 3
`Swim

Answer 5

APL, 35

4↑'SwimSink'⌽⍨4×x[3]>+/{+/⎕}¨⍳1⌷x←⎕

Not sure if allowed but it stops accepting input after the "city"

x←⎕ Takes input and store it in variable x (space-delimited numbers are interpreted as a numerical array)
1⌷ Extract index 1 (APL arrays are one-based)
⍳ Generate an array from 1 to the argument (1⌷x←⎕ in this case)
¨ "Map" operation
{+/⎕} Take array from input and return the sum
+/ Sum the array generated by the map operation
4×x[3]> Test if the sum < x[3] (returns 1 or 0), then multiply 4
'SwimSink'⌽⍨ Rotate the string 'SwimSink' by that amount
4↑ Finally, extract the first 4 characters of the string

Answer 6

AWK, 70

n{for(;NF;NF--)s+=$NF;n--}NR==1{n=$1;p=$3}END{print p<s?"Swim":"Sink"}

This is an imrovement by laindir on my submission (86):

NR==1{h=$1;w=$2;r=$3;next}NR<=h{for(i=1;i<=w;++i)c+=$i}END{print(c>r?"Swim":"Sink")}

Answer 7

CoffeeScript - 128 113

A function that takes the string as the only argument:

s=(l)->l=l.split /\n/;[n,m,p]=l[x=0].split /\s/;x+=c|0 for c in r.split /\s/ for r in l[1..n];`p>x?"Sink":"Swim"`

Answer 8

SED, 128

It was fun to write a sed version of this. It has the following short-comings:

• It assumes the city has more than two columns, to easily recognise rain lines.

• It assumes that the capacity of each city is in the range 0-9.

Here it is:

1d
s/^. .$/R/
G
:a
s/[\n 0]//
/[2-9]/{s/^/C/
y/23456789/12345678/}
s/1/C/
s/0//
s/RC//
h
ta
${s/R//g
s/^Sink//
s/.*C$/Swim/
p}

Call with the -n flag.

Answer 9

SWI-Prolog 79

If you don't mind the fact that this answer takes input by query, rather than via stdin:

s(A,L):-append(A,B),sumlist(B,C),length(L,D),(D>C->E='Sink';E='Swim'),print(E).

The answer doesn't validate input format, but I don't think it is a problem, since programming contest also doesn't require you to do so.

Sample query (using example in the question):

s([[3,2,3,4,5],
   [2,2,0,3,4],
   [1,1,2,3,3],
   [4,1,2,2,2],
   [4,1,1,2,2],
   [4,4,1,2,2],
   [4,4,2,2,2]],
  [(0,0),
   (1,2),
   (4,3)]).

Answer 10

Python - 152

import numpy
n, m, p = map(int,raw_input('').split())
print 'swim' if p<numpy.sum(numpy.matrix(';'.join([raw_input('') for i in range(n)]))) else 'sink'

Answer 11

Scala - 128

val a=readLine.split(' ')map(_.toInt);println(if((1 to a(0)map(x=>readLine.split(' ')map(_.toInt)sum)sum)>a(2))"swim"else"sink")

It might be possible to omit some parentheses or something but Scala is really fickle about punctuation and point-free style and () vs {} and whatnot.

Answer 12

Javascript - 73 Characters

for(i=c=0,a=s.split(/\s/);i++<a[0]*a[1];)c+=a[2+i]*1;c>a[2]?"Swim":"Sink"

Assumes the input is in the variable s and outputs Swim or Sink.

Example:

From the original question - entering this into the browser console:

s="7 5 3\n3 2 3 4 5\n2 2 0 3 4\n1 1 2 3 3\n4 1 2 2 2\n4 1 1 2 2\n4 4 1 2 2\n4 4 2 2 2\n0 0\n1 2\n4 3";
for(i=c=0,a=s.split(/\s/);i++<a[0]*a[1];)c+=a[2+i]*1;c>a[2]?"Swim":"Sink"

Outputs:

Swim