9
\$\begingroup\$

Taken from Google Code Jam 2013 Qualification Round Problem B:

Alice and Bob have a lawn in front of their house, shaped like an N metre by M metre rectangle. Each year, they try to cut the lawn in some interesting pattern. They used to do their cutting with shears, which was very time-consuming; but now they have a new automatic lawnmower with multiple settings, and they want to try it out.

The new lawnmower has a height setting - you can set it to any height h between 1 and 100 millimetres, and it will cut all the grass higher than h it encounters to height h. You run it by entering the lawn at any part of the edge of the lawn; then the lawnmower goes in a straight line, perpendicular to the edge of the lawn it entered, cutting grass in a swath 1m wide, until it exits the lawn on the other side. The lawnmower's height can be set only when it is not on the lawn.

Alice and Bob have a number of various patterns of grass that they could have on their lawn. For each of those, they want to know whether it's possible to cut the grass into this pattern with their new lawnmower. Each pattern is described by specifying the height of the grass on each 1m x 1m square of the lawn.

The grass is initially 100mm high on the whole lawn.

Write a function which takes a 2D array of integer heights and determines whether the lawn can be cut accordingly.

Here are 100 test cases from Google Code Jam. The first 35 cases should pass, the rest should not.

Shortest code wins.

\$\endgroup\$
  • 2
    \$\begingroup\$ Can you point out the licence under which the Google Code Jam problems are test cases are made available? \$\endgroup\$ – Peter Taylor Apr 15 '13 at 14:13
  • \$\begingroup\$ I've changed it to link to the problem rather than copying it directly. \$\endgroup\$ – cardboard_box Apr 15 '13 at 15:31
  • \$\begingroup\$ I think it is very unfortunate if the puzzle/question is presented here with only a link. The problem should be provided in full with all necessary detail. \$\endgroup\$ – Howard Apr 15 '13 at 15:34
  • 2
    \$\begingroup\$ "All problem statements, input data and contest analyses are licensed under the Creative Commons Attribution License." ~From the problem page \$\endgroup\$ – MrZander Apr 15 '13 at 22:00
9
\$\begingroup\$

J, 15 chars

   (-:>./"1<./>./)

Didn't expect this short solution.

Short explanation:

(input == ((max of rows of input) table with min of left and right (max in columns of input)))
(      -:          >./"1                        <./                       >./              )

If your function is 4 other function like in the solution: (f1 f2 f3 f4) and an input J computes it like f1(input,f3(f2(input),f4(input))) i.e. input f1 ((f2 input) f3 (f4 input)).

\$\endgroup\$
  • \$\begingroup\$ please explain the algorithm (I can't read J code ^^) \$\endgroup\$ – Olivier Dulac Apr 15 '13 at 8:21
  • 2
    \$\begingroup\$ @OlivierDulac Just added right now. \$\endgroup\$ – randomra Apr 15 '13 at 8:26
5
\$\begingroup\$

APL, 15 characters

{⍵≡(⌈/⍵)∘.⌊⌈⌿⍵}

Explanation:

  • ⌈⌿⍵ calculates the maximum of the columns of rhs
  • ⌈/⍵ does the same with rows
  • ∘.⌊ does the outer product of the previous two with respect to function minimum
  • ⍵≡ compares the result to the rhs

Examples:

      {⍵≡(⌈/⍵)∘.⌊⌈⌿⍵} 3 3 ⍴ 2 1 2 1 1 1 2 1 2
1

      {⍵≡(⌈/⍵)∘.⌊⌈⌿⍵} 2 3 ⍴ 2 2 2 2 1 1
0 
\$\endgroup\$
3
\$\begingroup\$

Python, 112 104

z=zip
y=lambda l:[[max(r)]*len(r)for r in l]
f=lambda l:l==[map(min,z(*r))for r in z(y(l),z(*y(z(*l))))]
\$\endgroup\$
  • 1
    \$\begingroup\$ Use map(min,z(*r)) instead of [min(a)for a in z(*r)] to save 8 characters \$\endgroup\$ – Volatility Apr 24 '13 at 12:34
0
\$\begingroup\$

I have a bit lengthier python code but it passed all the test cases given at Google Code Jam 2013.

 a=input();io=0
 while io<a:
     io+=1;[b,c]=map(int,raw_input("").strip().split());koi=[];koi1=[]
     for i in xrange(b):
         koi.append(map(int,raw_input("").strip().split()))
    rowmax=[]
    for i in koi:
        rowmax.append(max(i))
    for i in xrange(c):
        t=[]
        for j in koi:
            t.append(j[i])
        koi1.append(t);colmax=[]
    for i in koi1:
        colmax.append(max(i))
    toi1=[]
    for i in xrange(b):
        s=[]
        for j in xrange(c):
           s.append(min(colmax[j],rowmax[i]))
        toi1.append(s)
     if toi1==koi:
        print "Case #%d:"%io,"YES"
     else:
        print "Case #%d:"%io,"NO"
\$\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.