How many towers can you see?

Question

This question is based on the number-placement puzzle Towers (also known as Skyscrapers), which you can play online. Your goal is to take a solution to the puzzle and determine the clues -- the numbers of towers visible along each row and column. This is code golf, so fewest bytes wins.

How Towers works

The solution to a Towers puzzle is a Latin square -- a n*n grid in which every row and column contains a permutation of the numbers 1 through n. An example for n=5 is:

4 3 5 2 1 
5 4 1 3 2 
1 5 2 4 3 
2 1 3 5 4 
3 2 4 1 5 

Each row and column is labelled with a clue at each end like:

       2 3 1 4 5    
       v v v v v

 2 >   4 3 5 2 1   < 3
 1 >   5 4 1 3 2   < 4
 2 >   1 5 2 4 3   < 3
 3 >   2 1 3 5 4   < 2
 3 >   3 2 4 1 5   < 1 

       ^ ^ ^ ^ ^
       2 2 2 2 1

Each clue is a number from 1 to n that tells you how many towers you "see" looking along the row/column from that direction, if the numbers are treated as towers with that height. Each tower blocks shorter towers behind it. In other words, the towers you can see are the ones that are taller than any tower before them.

For example, let's look at the first row.

 2 >   4 3 5 2 1   < 3

It has a clue of 2 from the left because you can see the 4 and the 5. The 4 blocks the 3 from sight and the 5 blocks everything else. From the right, you can see 3 towers: 1, 2, and 5.

Program requirements

Write a program or function that takes in the grid of numbers and outputs or prints the clues, going clockwise from the top left.

Input

An n*n Latin-square with 2<=n<=9.

The format is flexible. You can use any data structure that represents a grid or list containing numbers or digit characters. You may require a separator between the rows or no separator at all. Some possibilities are a list, a list of lists, a matrix, a token-separated string like

43521 54132 15243 21354 32415,

or a string without spaces.

You're not given n as part of the input.

Output

Return or print the clues starting from the top left and going clockwise. So, first the upper clues reading rightwards, then the right clues reading downwards, then the lower clues reading leftwards, the the left clues reading upwards.

This would be 23145 34321 12222 33212 for the previous example

       2 3 1 4 5    
       v v v v v

 2 >   4 3 5 2 1   < 3
 1 >   5 4 1 3 2   < 4
 2 >   1 5 2 4 3   < 3
 3 >   2 1 3 5 4   < 2
 3 >   3 2 4 1 5   < 1 

       ^ ^ ^ ^ ^
       2 2 2 2 1

Just as for the input, you can use a list, string, or any ordered structure. The four "groups" can be separated or not, in a nested or a flat structure. But, the format must be the same for each group.

Example test cases:

(Your input/output format doesn't have to be the same as these.)

>> [[1 2] [2 1]]

[2 1]
[1 2]
[2 1]
[1 2]

>> [[3 1 2] [2 3 1] [1 2 3]]

[1 2 2]
[2 2 1]
[1 2 3]
[3 2 1]

>> [[4 3 5 2 1] [5 4 1 3 2] [1 5 2 4 3] [2 1 3 5 4] [3 2 4 1 5]]

[2 3 1 4 5]
[3 4 3 2 1]
[1 2 2 2 2]
[3 3 2 1 2]

>> [[2 6 4 1 3 7 5 8 9] [7 2 9 6 8 3 1 4 5] [5 9 7 4 6 1 8 2 3] [6 1 8 5 7 2 9 3 4] [1 5 3 9 2 6 4 7 8] [3 7 5 2 4 8 6 9 1] [8 3 1 7 9 4 2 5 6] [9 4 2 8 1 5 3 6 7] [4 8 6 3 5 9 7 1 2]]

[4 2 2 3 3 3 3 2 1]
[1 3 3 2 2 2 2 3 3]
[4 3 2 1 2 3 3 2 2]
[3 1 2 4 3 3 2 2 5]

For you convenience, here are the same test cases in a flat string format.

>> 1221

21
12
21
12

>> 312231123

122
221
123
321

>> 4352154132152432135432415

23145
34321
12222
33212

>> 264137589729683145597461823618572934153926478375248691831794256942815367486359712

422333321
133222233
432123322
312433225

Answer 1

APL 19

≢¨∪/⌈\(⍉⍪⌽⍪⊖∘⌽∘⍉⍪⊖)

(golfed a bit more after ngn's suggestion, thanks)

Explanation:

(⍉⍪⌽⍪⊖∘⌽∘⍉⍪⊖)  rotates matrix 4 times appending results
⌈\ gets maximums for each row up to current column (example: 4 2 3 5 1 gives 4 4 4 5 5)
≢¨∪/ counts unique elements for each row

Try it on tryapl.org

Answer 2

Python 2, 115 bytes

def T(m):o=[];exec'm=zip(*m)[::-1]\nfor r in m[::-1]:\n n=k=0\n for x in r:k+=x>n;n=max(x,n)\n o+=[k]\n'*4;return o

There's an awful lot of list flipping going on in there.

Takes input as a nested list (e.g. call with T([[4,3,5,2,1],[5,4,1,3,2],[1,5,2,4,3],[2,1,3,5,4],[3,2,4,1,5]])). Output is a single flat list.

Ungolfed:

def T(m):
 o=[]
 for _ in [0]*4:
  m=zip(*m)[::-1]
  for r in m[::-1]:
   n=k=0
   for x in r:k+=x>n;n=max(x,n)
   o+=[k]
 return o

Alternative 115:

def T(m):o=[];exec'm=zip(*m)[::-1];o+=[len(set([max(r[:i+1])for i in range(len(r))]))for r in m[::-1]];'*4;return o

I have no idea why this works with a list comprehension, but chucks a NameError with a set comprehension...

A bit too long, but if anyone's interested — yes, it's possible to get this down to a lambda!

T=lambda m:[len({max(r[:i+1])for i in range(len(r))})for k in[1,2,3,4]for r in eval("zip(*"*k+"m"+")[::-1]"*k)[::-1]]

---

Pyth, 25 bytes

V4=Q_CQ~Yml{meS<dhkUd_Q)Y

Obligatory Pyth port.

Input the list via STDIN, e.g. [[4, 3, 5, 2, 1], [5, 4, 1, 3, 2], [1, 5, 2, 4, 3], [2, 1, 3, 5, 4], [3, 2, 4, 1, 5]].

Try it online... is what I would say but unfortunately, for security reasons, the online interpreter disallows the use of eval on nested brackets. Try the workaround code JcQ5V4=J_CJ~Yml{meS<dhkUd_J)Y instead, and input as a flattened list like [4, 3, 5, 2, 1, 5, 4, 1, 3, 2, 1, 5, 2, 4, 3, 2, 1, 3, 5, 4, 3, 2, 4, 1, 5].

(Thanks to @isaacg who helped golf out a few bytes)

Answer 3

CJam, 29 27 bytes

q~{z_{[{1$e>}*]_&,}%pW%}4*;

Input like

[[4 3 5 2 1] [5 4 1 3 2] [1 5 2 4 3] [2 1 3 5 4] [3 2 4 1 5]]

Output like

[2 3 1 4 5]
[3 4 3 2 1]
[1 2 2 2 2]
[3 3 2 1 2]

How it works

The basic idea is to have the code work along rows and rotate the grid counter-clockwise 4 times. To count the towers, I'm raising each tower as far as it doesn't make a "visual difference" (i.e., don't change it if it's visible, or pull it up to the same height of the tower in front of it), and then I'm counting distinct heights.

q~                          "Read and evaluate the input.";
  {                    }4*  "Four times...";
   z                        "Transpose the grid.";
    _                       "Duplicate.";
     {            }%        "Map this block onto each row.";
      [       ]             "Collect into an array.";
       {    }*              "Fold this block onto the row.";
        1$                  "Copy the second-to-topmost element.":
          e>                "Take the maximum of the top two stack elements.";
                            "This fold replaces each element in the row by the
                             maximum of the numbers up to that element. So e.g.
                             [2 1 3 5 4] becomes [2 2 3 5 5].";
               _&,          "Count unique elements. This is how many towers you see.";
                    p       "Print array of results.";
                     W%     "Reverse the rows for the next run. Together with the transpose at
                             the start this rotates the grid counter-clockwise.";
                          ; "Get rid of the grid so that it isn't printed at the end.";

Answer 4

APL, 44

{{+/~0∊¨↓(∘.>⍨⍵)≥∘.<⍨⍳⍴⍵}¨↓(⌽∘⍉⍪⊢⍪⊖∘⍉⍪⊖∘⌽)⍵}

Tested here.

Answer 5

J, 35 chars

(+/@((>./={:)\)"2@(|.@|:^:(<4)@|:))

Example:

   t=.4 3 5 2 1,. 5 4 1 3 2,. 1 5 2 4 3,. 2 1 3 5 4,. 3 2 4 1 5
   (+/@((>./={:)\)"2@(|.@|:^:(<4)@|:)) t
2 3 1 4 5
3 4 3 2 1
1 2 2 2 2
3 3 2 1 2

Try it here.

Answer 6

Haskell, 113

import Data.List
f(x:s)=1+f[r|r<-s,r>x]
f _=0
r=reverse
t=transpose
(?)=map
l s=[f?t s,(f.r)?s,r$(f.r)?t s,r$f?s]

Answer 7

Mathematica, 230,120,116,113 110 bytes

f=(t=Table;a=#;s=Length@a;t[v=t[c=m=0;t[h=a[[y,x]];If[h>m,c++;m=h],{y,s}];c,{x,s}];a=Thread@Reverse@a;v,{4}])&

Usage:

f[{
  {4, 3, 5, 2, 1},
  {5, 4, 1, 3, 2},
  {1, 5, 2, 4, 3},
  {2, 1, 3, 5, 4},
  {3, 2, 4, 1, 5}
}]

{{2, 3, 1, 4, 5}, {3, 4, 3, 2, 1}, {1, 2, 2, 2, 2}, {3, 3, 2, 1, 2}}

Answer 8

JavaScript, 335 264 256 213

T=I=>((n,O)=>(S=i=>i--&&O.push([])+S(i)+(R=(j,a,x)=>j--&&R(j,0,0)+(C=k=>k--&&((!(a>>(b=I[(F=[f=>n-k-1,f=>j,f=>k,f=>n-j-1])[i]()][F[i+1&3]()])))&&++x+(a=1<<b))+C(k))(n)+O[i].push(x))(n,0,0))(4)&&O)(I.length,[],[])

Evaluate in the browser's JavaScript console (I used Firefox 34.0, doesn't seem to work in Chrome 39??) Test with:

JSON.stringify(T([[4, 3, 5, 2, 1], [5, 4, 1, 3, 2], [1, 5, 2, 4, 3], [2, 1, 3, 5, 4], [3, 2, 4, 1, 5]]));

Here's the current incarnation of the ungolfed code - it's getting harder to follow:

function countVisibleTowers(input) {
  return ((n, out) =>
      (sideRecurse = i =>
          i-- &&
          out.push([]) +
          sideRecurse(i) +
          (rowRecurse = (j, a, x) =>
              j-- &&
              rowRecurse(j, 0, 0) +
              (columnRecurse = k =>
                  k-- &&
                  ((!(a >> (b = input[
                                        (offsetFtn = [
                                            f => n - k - 1,   // col negative
                                            f => j,           // row positive
                                            f => k,           // col positive
                                            f => n - j - 1    // row negative
                                        ])[i]()
                                     ]
                                     [
                                        offsetFtn[i + 1 & 3]()
                                     ]))) &&
                  ++x +
                  (a = 1 << b)) +
                  columnRecurse(k)
              )(n) +
              out[i].push(x)
          )(n, 0, 0)
      )(4) && out
  )(input.length, [], [])
}

I intentionally didn't look at any of the other answers, I wanted to see if I could work something out myself. My approach was to flatten the input arrays to a one-dimensional array and precompute offsets to the rows from all four directions. Then I used shift right to test whether the next tower was falsy and if it was, then increment the counter for each row.

I am hoping there is lots of ways to improve this, perhaps not precalculate the offsets, but rather use some sort of overflow/modulo on the 1D input array? And perhaps combine my loops, get more functional, deduplicate.

Any suggestions would be appreciated!

Update #1 : Progress, we have the technology! I was able to get rid of the precalculated offsets and do them inline with ternary operators strung together. Also was able to get rid of my if statement and convert the for loops into whiles.

Update #2 : This is pretty frustrating; no pizza party for me. I figured going functional and using recursion would shave off many bytes, but my first few tries ended up being larger by as much as 100 characters! In desperation, I went whole-hog on using ES6 fat arrow functions to really pare it down. Then I took to replacing boolean operators with arithmetic ones and removing parens, semi-colons and spaces whereever I could. I even quit declaring my vars and polluted the global namespace with my local symbols. Dirty, dirty. After all that effort, I beat my Update #1 score by a whopping 8 characters, down to 256. Blargh!

If I applied the same ruthless optimizations and ES6 tricks to my Update #1 function, I'd beat this score by a mile. I may do an Update #3 just to see what that would look like.

Update #3 : Turns out the fat arrow recursive approach had lots more life in it, I just needed to work with the 2 dimensional input directly rather than flattening it and get better about leveraging the closure scopes. I rewrote the inner array offset calculations twice and got the same score, so this approach may be close to minned out!

Answer 9

Java, only 352 350 325 bytes...

class S{public static void main(String[]a){int n=a.length,i=0,j,k,b,c;int[][]d=new int[n][n];for(;i<n;i++)for(j=0;j<n;)d[i][j]=a[i].charAt(j++);for(i=0;i<4;i++){int[][]e=new int[n][n];for(k=0;k<n;k++)for(j=0;j<n;)e[n-j-1][k]=d[k][j++];d=e;for(j=n;j-->(k=c=b=0);System.out.print(c))for(;k<n;k++)b=d[j][k]>b?d[j][k]+0*c++:b;}}}

Input like 43521 54132 15243 21354 32415

Output like: 23145343211222233212

Indented:

class S{
    public static void main(String[]a){
        int n=a.length,i=0,j,k,b,c;
        int[][]d=new int[n][n];
        for(;i<n;i++)
            for(j=0;j<n;)d[i][j]=a[i].charAt(j++);
        for(i=0;i<4;i++){
            int[][]e=new int[n][n];
            for(k=0;k<n;k++)
                for(j=0;j<n;)e[n-j-1][k]=d[k][j++];
            d=e;
            for(j=n;j-->(k=c=b=0);System.out.print(c))
                for(;k<n;k++)b=d[j][k]>b?d[j][k]+0*c++:b;
        }
    }
}

Any tips would be greatly appreciated!

Answer 10

Python 2 - 204 bytes

def f(l):n=len(l);k=[l[c]for c in range(n)if l[c]>([0]+list(l))[c]];return f(k)if k!=l else n
r=lambda m:(l[::-1]for l in m)
m=input();z=zip(*m);n=0
for t in z,r(m),r(z),m:print map(f,t)[::1-(n>1)*2];n+=1

This is probably a really poor golf. I thought the problem was interesting, so I decided to tackle it without looking at anyone else's solution. As I type this sentence I have yet to look at the answers on this question. I wouldn't be surprised if someone else has already done a shorter Python program ;)

I/O Example

$ ./towers.py <<< '[[4,3,5,2,1],[5,4,1,3,2],[1,5,2,4,3],[2,1,3,5,4],[3,2,4,1,5]]'
[2, 3, 1, 4, 5]
[3, 4, 3, 2, 1]
[1, 2, 2, 2, 2]
[3, 3, 2, 1, 2]

You may optionally include whitespace in the input. Pretty much anywhere, honestly. So long as you can eval() it, it'll work.

Explanation

The only interesting part of this program is the first line. It defines a function f(l) that tells you how many towers can be seen in a row, and the rest of the program is just applying that function to every possible position.

When called, it finds the length of l and saves it in a variable n. Then it creates a new variable k with this pretty monstrous list comprehension:

[l[c]for c in range(n)if l[c]>([0]+list(l))[c]]

It's not too bad when you break it down. Since n==len(l), everything before the if just represents l. However, using if we can remove some elements from the list. We construct a list with ([0]+list(l)), which is just "l with a 0 added to the beginning" (ignore the call to list(), that's only there because sometimes l is a generator and we need to make sure it's actually a list here). l[c] is only put into the final list if it's greater than ([0]+list(l))[c]. This does two things:

• Since there's a new element at the beginning of the list, the index of each l[c] becomes c+1. We're effectively comparing each element to the element to the left of it. If it's greater, it's visible. Otherwise it's hidden and removed from the list.
• The first tower is always visible because there's nothing that can block it. Because we put 0 at the beginning, the first tower is always greater. (If we didn't do this [0]+ nonsense and just compared l[c] to l[c-1], Python would compare the first tower to the last one (you can index into a list from the end with -1, -2, etc.), so if the last tower was taller than the first one we'd get the wrong result.

When all is said and done, l contains some number of towers and k contains each one of those that isn't shorter than its immediate neighbour to the left. If none of them were (e.g. for f([1,2,3,4,5])), then l == k. We know there's nothing left to do and return n (the length of the list). If l != k, that means at least one of the towers was removed this time around and there may be more to do. So, we return f(k). God, I love recursion. Interestingly, f always recurses one level deeper than is strictly "necessary". When the list that will be returned is generated, the function has no way of knowing that at first.

When I started writing this explanation, this program was 223 bytes long. While explaining things I realized that there were ways to save characters, so I'm glad I typed this up! The biggest example is that f(l) was originally implemented as an infinite loop that was broken out of when the computation was done, before I realized recursion would work. It just goes to show that the first solution you think of won't always be the best. :)

Answer 11

Matlab, (123)(119)

function r=m(h);p=[h rot90(h) rot90(h,2) rot90(h,3)];for i=2:size(p) p(i,:)=max(p(i,:),p(i-1,:));end;r=sum(diff(p)>0)+1

used like this:

m([
 4     3     5     2     1;
 5     4     1     3     2;
 1     5     2     4     3;
 2     1     3     5     4;
 3     2     4     1     5])

 [2 3 1 4 5 3 4 3 2 1 1 2 2 2 2 3 3 2 1 2]

C#, down to 354...

Different approach than TheBestOne used.

using System;
using System.Linq;

class A
{
    static void Main(string[] h)
    {
        int m = (int)Math.Sqrt(h[0].Length),k=0;
        var x = h[0].Select(c => c - 48);
        var s = Enumerable.Range(0, m);
        for (; k < 4; k++)
        {
            (k%2 == 0 ? s : s.Reverse())
                .Select(j =>
                        (k > 0 && k < 3 ? x.Reverse() : x).Where((c, i) => (k % 2 == 0 ? i % m : i / m) == j)
                                                          .Aggregate(0, (p, c) =>
                                                                        c > p%10
                                                                            ? c + 10 + p/10*10
                                                                            : p, c => c/10))
                .ToList()
                .ForEach(Console.Write);
        }
    }
}