Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
    
Is it n lines of m values or the other way around? Your example doesn't match the written specification. –  algorithmshark Mar 6 at 23:54
    
@algorithmshark Corrected –  Rainbolt Mar 6 at 23:56
13  
I'm not sure, but it seems to me that you sink if the amount of rain is larger than the sum of rain that all the squares can hold; otherwise you float. Is this it? –  hosch250 Mar 6 at 23:59
2  
@hosch250 Spoiling the fun! –  Rainbolt Mar 7 at 0:50
1  
"The excess water is evenly distributed to its neighbors." - that is likely to be 1 unit of water. Does it distribute as e.g. 0.25 units to each adjacent cell (assuming a single middle flooded cell)? –  Neil Slater Mar 7 at 9:44

12 Answers 12

up vote 16 down vote accepted

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.

share|improve this answer
    
] without a matching [ will collect the entire stack into an array, so an initial [~] can be simplified to ~]. To get the first grid_size elements of an array, use <, so <{+}* can almost certainly save you a bit on adding the total capacity. 0>"Sink""Swim"if can be 0>"SinkSwim"4/= –  Peter Taylor Mar 7 at 9:26
    
@PeterTaylor: Thanks for the tips! Are you sure about ~]? I tried it and it didn't seem to work. The last hack is nice though it has to be "SwimSink" - will use it. and the array thing also seems promising, will get to work on that. –  Claudiu Mar 7 at 17:27
    
I'm certain: that's a standard trick which I and others have been using for years. –  Peter Taylor Mar 7 at 18:10
    
@PeterTaylor: Hmm strange. Try it in the interpreter I linked to - it fails. Then - ok maybe the web interpreter is non-standard. But I tried also with ruby golfscript.rb and it still didn't work... can you verify that it works on your end? I get same error on both: undefined method '+' for nil:NilClass (NoMethodError) –  Claudiu Mar 7 at 18:23
1  
When you insert a string literal to substitute for lack of stdin, you should precede it with a semicolon to remove the empty string which actually comes "from stdin". With that it works fine –  Peter Taylor Mar 7 at 18:41

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 **.

share|improve this answer
3  
96 - p;main(n,m){for(scanf("%d%d%d",&n,&m,&p),n*=m;n--;scanf("%d",&m),p-=m);puts(p>0‌​?"Sink":"Swim");} –  aragaer Mar 7 at 8:44
1  
95 - n,m;main(p){for(scanf("%d%d%d",&n,&m,&p),n*=m;n--;scanf("%d",&m))p-=m;puts(p>0?‌​"Sink":"Swim");}. I've also played with idea of n-=scanf, but not sure if program will be correct after that. First scanf can be moved to the front of for without changing the character count. –  aragaer Mar 9 at 21:19
    
n-=scanf... wouldn't work, as n-=1 basically is a pre-increment, so it would miss the south-eastern corner. The other change is great. –  Fors Mar 9 at 22:32

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.

share|improve this answer
9  
I was on one of the 40+ teams. We were GIVEN the catch after failing. Everyone in the auditorium facepalmed simultaneously. I think perhaps I shouldn't have mentioned it here. You guys were too quick! –  Rainbolt Mar 6 at 23:40
    
Ouch! By the way, should I get the input from stdin for these sort of questions? - I'm new to stackexchange. :) –  swalladge Mar 6 at 23:50
    
I was going to edit my question to say specify STDIN, but I feared that it would invalidate your answer. I have been reading puzzles here for about a month, and haven't really noticed if people specified STDIN or not. –  Rainbolt Mar 6 at 23:53
1  
@swalladge Welcome to Codegolf! I recommend making the headline a headline by prepending a #. –  TimWolla Mar 7 at 0:23
2  
You can bring it down to 108 if you use input() and map(): n,_,p=map(int,input().split());print(['sink','swim'][p>sum(sum(map(int,input().‌​split()))for a in range(n))]) –  Blender Mar 7 at 1:32

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
share|improve this answer

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"`
share|improve this answer
    
You can remove the indentation, and move everything on first line separated by semicolons. You also write `p>x?"Sink":"Swim"` instead of if p>x then"Sink"else"Swim". Parens for the third statement also aren't needed. –  xfix Mar 9 at 9:18
    
@xfix Thanks a lot. –  TimWolla Mar 9 at 13:35

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")}
share|improve this answer
    
NR<=h should be NR<=h+1, otherwise you'll get false Sinks as the last line of capacities is skipped. This can also be shortened to 70 as n{for(;NF;NF--)s+=$NF;n--}NR==1{n=$1;p=$3}END{print p<s?"Swim":"Sink"} –  laindir Mar 12 at 14:26
1  
@laindir Well, thank you very much for the improvement! I find it so fun, that Awk just comes next to APL, J and K, which were breeded to beat everyone on code-golfing! :-) –  user40989 Mar 12 at 14:58

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

share|improve this answer
    
I think the only part that matters is that it outputs the correct answer for any given input. If this is unusual for CodeGolf, hopefully someone will let me know. –  Rainbolt Mar 7 at 14:08

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)]).
share|improve this answer

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.

share|improve this answer

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'
share|improve this answer
1  
You could start by taking out some whitespace. After ,, before and after ', after ) –  minitech Mar 7 at 19:09

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.

share|improve this answer

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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