39
\$\begingroup\$

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.

\$\endgroup\$
10
  • \$\begingroup\$ Is it n lines of m values or the other way around? Your example doesn't match the written specification. \$\endgroup\$ Mar 6, 2014 at 23:54
  • \$\begingroup\$ @algorithmshark Corrected \$\endgroup\$
    – Rainbolt
    Mar 6, 2014 at 23:56
  • 13
    \$\begingroup\$ 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? \$\endgroup\$
    – user10766
    Mar 6, 2014 at 23:59
  • 2
    \$\begingroup\$ @hosch250 Spoiling the fun! \$\endgroup\$
    – Rainbolt
    Mar 7, 2014 at 0:50
  • 1
    \$\begingroup\$ "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)? \$\endgroup\$ Mar 7, 2014 at 9:44

12 Answers 12

20
\$\begingroup\$

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

\$\endgroup\$
3
  • 3
    \$\begingroup\$ 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");} \$\endgroup\$
    – aragaer
    Mar 7, 2014 at 8:44
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – aragaer
    Mar 9, 2014 at 21:19
  • \$\begingroup\$ 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. \$\endgroup\$
    – Fors
    Mar 9, 2014 at 22:32
16
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ ] 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/= \$\endgroup\$ Mar 7, 2014 at 9:26
  • \$\begingroup\$ @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. \$\endgroup\$
    – Claudiu
    Mar 7, 2014 at 17:27
  • \$\begingroup\$ I'm certain: that's a standard trick which I and others have been using for years. \$\endgroup\$ Mar 7, 2014 at 18:10
  • \$\begingroup\$ @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) \$\endgroup\$
    – Claudiu
    Mar 7, 2014 at 18:23
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ Mar 7, 2014 at 18:41
7
\$\begingroup\$

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.

\$\endgroup\$
7
  • 10
    \$\begingroup\$ 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! \$\endgroup\$
    – Rainbolt
    Mar 6, 2014 at 23:40
  • \$\begingroup\$ Ouch! By the way, should I get the input from stdin for these sort of questions? - I'm new to stackexchange. :) \$\endgroup\$
    – user18498
    Mar 6, 2014 at 23:50
  • \$\begingroup\$ 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. \$\endgroup\$
    – Rainbolt
    Mar 6, 2014 at 23:53
  • 1
    \$\begingroup\$ @swalladge Welcome to Codegolf! I recommend making the headline a headline by prepending a #. \$\endgroup\$
    – TimWolla
    Mar 7, 2014 at 0:23
  • 2
    \$\begingroup\$ 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))]) \$\endgroup\$
    – Blender
    Mar 7, 2014 at 1:32
6
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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

\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$
    – Rainbolt
    Mar 7, 2014 at 14:08
  • \$\begingroup\$ Change ⎕IO←0, then replace 4↑'SwimSink'⌽⍨4× with 'Swim' 'Sink'⊃⍨, x[3] with x[2], and 1⌷x with ⊃x to save two bytes. \$\endgroup\$
    – Adám
    Nov 19, 2016 at 20:19
  • \$\begingroup\$ @Rainbolt : this entry is 53 bytes long - measuring by utf-8 chars makes this one "appear" more compact when it fact it takes more space than the best entries for J+K above - J is 50 bytes worth of ASCII \$\endgroup\$ Nov 1, 2022 at 12:47
  • \$\begingroup\$ @RAREKpopManifesto Why are you telling me this? Did I post a leaderboard somewhere? \$\endgroup\$
    – Rainbolt
    Nov 1, 2022 at 15:51
  • \$\begingroup\$ @Rainbolt : you're OP right ? so I presumed, apparently inaccurately, that you might have a say regarding the challenge/contest you posted \$\endgroup\$ Nov 1, 2022 at 20:23
6
\$\begingroup\$

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")}
\$\endgroup\$
3
  • \$\begingroup\$ 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"} \$\endgroup\$
    – laindir
    Mar 12, 2014 at 14:26
  • 1
    \$\begingroup\$ @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! :-) \$\endgroup\$
    – user40989
    Mar 12, 2014 at 14:58
  • \$\begingroup\$ @user40989 I don't understand. Awk seem 40-100% longer than J/K/APL, even though they are not golfing languages, but rather (stem from) commercial programming languages. \$\endgroup\$
    – Adám
    Nov 19, 2016 at 20:23
5
\$\begingroup\$

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"`
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – 0..
    Mar 9, 2014 at 9:18
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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)]).
\$\endgroup\$
1
\$\begingroup\$

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'
\$\endgroup\$
1
  • 1
    \$\begingroup\$ You could start by taking out some whitespace. After ,, before and after ', after ) \$\endgroup\$
    – Ry-
    Mar 7, 2014 at 19:09
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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