Hide the buildings
up vote
15
down vote
favorite
Shorter version of Skyscrapers Challenge
Task
Given an array of building heights and a positive integer k
, find all the permutations(without duplicates) of the heights such that exactly k
buildings are visible.
Any building will hide all shorter or equal height buildings behind it.
Any format for input and output is valid.
Input array will never be empty.
In case it is not possible to see exactly as many buildings, output anything that cannot be an answer but no error.
Examples:
(Length of output is shown for very long outputs,but your output should be all possible permutations)
input:[1,2,3,4,5],2
output: 50
input:[5,5,5,5,5,5,5,5],2
output:
input:[1,2,2],2
output:[(1,2,2)]
Seeing from the left, exactly 2 buildings are visible.
input:[1,7,4],2
output:[(4, 7, 1), (1, 7, 4), (4, 1, 7)]
input:[1,2,3,4,5,6,7,8,9],4
output:67284
input:[34,55,11,22],1
output:[(55, 34, 11, 22), (55, 22, 34, 11), (55, 34, 22, 11), (55, 11, 34, 22), (55, 22, 11, 34), (55, 11, 22, 34)]
input:[3,4,1,2,3],2
output:31
This is code-golf so shortest code wins
Optional: If possible, can you add something like if length is greater than 20: print length else print answer
. In the footer, not in the code.
code-golf permutations
add a comment |
up vote
15
down vote
favorite
Shorter version of Skyscrapers Challenge
Task
Given an array of building heights and a positive integer k
, find all the permutations(without duplicates) of the heights such that exactly k
buildings are visible.
Any building will hide all shorter or equal height buildings behind it.
Any format for input and output is valid.
Input array will never be empty.
In case it is not possible to see exactly as many buildings, output anything that cannot be an answer but no error.
Examples:
(Length of output is shown for very long outputs,but your output should be all possible permutations)
input:[1,2,3,4,5],2
output: 50
input:[5,5,5,5,5,5,5,5],2
output:
input:[1,2,2],2
output:[(1,2,2)]
Seeing from the left, exactly 2 buildings are visible.
input:[1,7,4],2
output:[(4, 7, 1), (1, 7, 4), (4, 1, 7)]
input:[1,2,3,4,5,6,7,8,9],4
output:67284
input:[34,55,11,22],1
output:[(55, 34, 11, 22), (55, 22, 34, 11), (55, 34, 22, 11), (55, 11, 34, 22), (55, 22, 11, 34), (55, 11, 22, 34)]
input:[3,4,1,2,3],2
output:31
This is code-golf so shortest code wins
Optional: If possible, can you add something like if length is greater than 20: print length else print answer
. In the footer, not in the code.
code-golf permutations
Should the output be all qualifying permutations, or the number thereof?
– Luis Mendo
Nov 15 at 6:49
It should be all qualifying permutations @LuisMendo
– Vedant Kandoi
Nov 15 at 6:54
Suggested test case:[1,2,3,4,5],5 -> [(1,2,3,4,5)]
. None of the current test cases ensure that answers can support showing all buildings (though I don't know whether any actually have a problem with that).
– Kamil Drakari
Nov 15 at 15:27
add a comment |
up vote
15
down vote
favorite
up vote
15
down vote
favorite
Shorter version of Skyscrapers Challenge
Task
Given an array of building heights and a positive integer k
, find all the permutations(without duplicates) of the heights such that exactly k
buildings are visible.
Any building will hide all shorter or equal height buildings behind it.
Any format for input and output is valid.
Input array will never be empty.
In case it is not possible to see exactly as many buildings, output anything that cannot be an answer but no error.
Examples:
(Length of output is shown for very long outputs,but your output should be all possible permutations)
input:[1,2,3,4,5],2
output: 50
input:[5,5,5,5,5,5,5,5],2
output:
input:[1,2,2],2
output:[(1,2,2)]
Seeing from the left, exactly 2 buildings are visible.
input:[1,7,4],2
output:[(4, 7, 1), (1, 7, 4), (4, 1, 7)]
input:[1,2,3,4,5,6,7,8,9],4
output:67284
input:[34,55,11,22],1
output:[(55, 34, 11, 22), (55, 22, 34, 11), (55, 34, 22, 11), (55, 11, 34, 22), (55, 22, 11, 34), (55, 11, 22, 34)]
input:[3,4,1,2,3],2
output:31
This is code-golf so shortest code wins
Optional: If possible, can you add something like if length is greater than 20: print length else print answer
. In the footer, not in the code.
code-golf permutations
Shorter version of Skyscrapers Challenge
Task
Given an array of building heights and a positive integer k
, find all the permutations(without duplicates) of the heights such that exactly k
buildings are visible.
Any building will hide all shorter or equal height buildings behind it.
Any format for input and output is valid.
Input array will never be empty.
In case it is not possible to see exactly as many buildings, output anything that cannot be an answer but no error.
Examples:
(Length of output is shown for very long outputs,but your output should be all possible permutations)
input:[1,2,3,4,5],2
output: 50
input:[5,5,5,5,5,5,5,5],2
output:
input:[1,2,2],2
output:[(1,2,2)]
Seeing from the left, exactly 2 buildings are visible.
input:[1,7,4],2
output:[(4, 7, 1), (1, 7, 4), (4, 1, 7)]
input:[1,2,3,4,5,6,7,8,9],4
output:67284
input:[34,55,11,22],1
output:[(55, 34, 11, 22), (55, 22, 34, 11), (55, 34, 22, 11), (55, 11, 34, 22), (55, 22, 11, 34), (55, 11, 22, 34)]
input:[3,4,1,2,3],2
output:31
This is code-golf so shortest code wins
Optional: If possible, can you add something like if length is greater than 20: print length else print answer
. In the footer, not in the code.
code-golf permutations
code-golf permutations
edited Nov 15 at 7:23
asked Nov 15 at 6:34
Vedant Kandoi
54714
54714
Should the output be all qualifying permutations, or the number thereof?
– Luis Mendo
Nov 15 at 6:49
It should be all qualifying permutations @LuisMendo
– Vedant Kandoi
Nov 15 at 6:54
Suggested test case:[1,2,3,4,5],5 -> [(1,2,3,4,5)]
. None of the current test cases ensure that answers can support showing all buildings (though I don't know whether any actually have a problem with that).
– Kamil Drakari
Nov 15 at 15:27
add a comment |
Should the output be all qualifying permutations, or the number thereof?
– Luis Mendo
Nov 15 at 6:49
It should be all qualifying permutations @LuisMendo
– Vedant Kandoi
Nov 15 at 6:54
Suggested test case:[1,2,3,4,5],5 -> [(1,2,3,4,5)]
. None of the current test cases ensure that answers can support showing all buildings (though I don't know whether any actually have a problem with that).
– Kamil Drakari
Nov 15 at 15:27
Should the output be all qualifying permutations, or the number thereof?
– Luis Mendo
Nov 15 at 6:49
Should the output be all qualifying permutations, or the number thereof?
– Luis Mendo
Nov 15 at 6:49
It should be all qualifying permutations @LuisMendo
– Vedant Kandoi
Nov 15 at 6:54
It should be all qualifying permutations @LuisMendo
– Vedant Kandoi
Nov 15 at 6:54
Suggested test case:
[1,2,3,4,5],5 -> [(1,2,3,4,5)]
. None of the current test cases ensure that answers can support showing all buildings (though I don't know whether any actually have a problem with that).– Kamil Drakari
Nov 15 at 15:27
Suggested test case:
[1,2,3,4,5],5 -> [(1,2,3,4,5)]
. None of the current test cases ensure that answers can support showing all buildings (though I don't know whether any actually have a problem with that).– Kamil Drakari
Nov 15 at 15:27
add a comment |
9 Answers
9
active
oldest
votes
up vote
6
down vote
05AB1E, 10 9 bytes
œÙʒη€àÙgQ
Try it online or verify (almost) all test cases (test case [1,2,3,4,5,6,7,8,9],4
times out).
Footer of the TIO does what OP asked at the bottom:
Optional: If possible, can you add something like
if length is greater than 20: print length else print answer
. In the footer, not in the code.
Explanation:
œ # Permutations of the (implicit) input-list
# i.e. [1,2,2] → [[1,2,2],[1,2,2],[2,1,2],[2,2,1],[2,1,2],[2,2,1]]
Ù # Only leave the unique permutations
# i.e. [[1,2,2],[1,2,2],[2,1,2],[2,2,1],[2,1,2],[2,2,1]]
# → [[1,2,2],[2,1,2],[2,2,1]]
ʒ # Filter it by:
η # Push the prefixes of the current permutation
# i.e. [1,2,2] → [[1],[1,2],[1,2,2]]
ۈ # Calculate the maximum of each permutation
# i.e. [[1],[1,2],[1,2,2]] → [1,2,2]
Ù # Only leave the unique maximums
# i.e. [1,2,2] → [1,2]
g # And take the length
# i.e. [1,2] → 2
Q # And only leave those equal to the second (implicit) input
# i.e. 2 and 2 → 1 (truthy)
1
Impressive, every single byte here is part of the function tree!
– lirtosiast
Nov 15 at 9:23
1
@lirtosiast Yeah, 05AB1E has some pretty short builtins sometimes, which were perfect in this challenge. :) It's actually very similar to your Pyth answer I see. Funny thing is, is that the footer forif length is greater than 20: print length; else print answer;
is a̶ ̶b̶y̶t̶e̶ ̶l̶o̶n̶g̶e̶r̶ of equal length in comparison to the program itself. xD
– Kevin Cruijssen
Nov 15 at 9:25
add a comment |
up vote
5
down vote
Haskell, 73 bytes
import Data.List
f n=filter((n==).length.nub.scanl1 max).nub.permutations
Try it online!
add a comment |
up vote
5
down vote
Jelly, 12 10 bytes
Œ!Q»QL=ʋƇ
Try it online!
-2 bytes by @Erik the Outgolfer
This is a dyadic function taking the building heights and k
in that order.
Œ! All permutations of first input
Œ!Q Unique permutations of first input
» Running maximum
Q Unique values
L Length of this array
= Equals k
ʋ Create a monad from these 4 links
»QL=ʋ "Are exactly k buildings visible in arrangement x?"
Ƈ Filter if f(x)
Œ!Q»QL=ʋƇ All distinct perms of first input with k visible buildings.
1
Hail the newʋ
! (it's pretty older thanƇ
, actually :P)
– Erik the Outgolfer
Nov 15 at 12:36
add a comment |
up vote
4
down vote
Pyth, 18 16 bytes
fqvzl{meSd._T{.p
Try it here.
Note that the online version of the Pyth interpreter throws a memory error on the largest test case.
f Filter lambda T:
q Are second input and # visible buildings equal?
v z The second input value
l { The number of unique elements in
m the maximums
e S d ...
._ T of prefixes of T
{ .p over unique permutations of (implicit first input)
Welcome back! :-)
– Luis Mendo
Nov 15 at 12:49
add a comment |
up vote
2
down vote
Perl 6, 81 63 bytes
-18 bytes thanks to nwellnhof!
{;*.permutations.unique(:with(*eqv*)).grep:{$_==set [max] @_}}
Try it online!
Anonymous code block that takes input curried, e.g. f(n)(list)
. That .unique(:with(*eqv*))
is annoyingly long though :(
Explanation:
{; } # Anonymous code block
*.permutations.unique(:with(*eqv*)) # From all distinct permutations
.grep:{ } # Filter where
set [max] @_ # Visible buildings
$_== # Equals num
1
FWIW, I just filed a Rakudo issue so we might get rid of that annoying;
eventually ;)
– nwellnhof
Nov 15 at 9:55
add a comment |
up vote
2
down vote
Japt, 11 bytes
á f_åÔâ Ê¥V
Try it online!
For the longer outputs, adding } l
to the end will output the length instead. The online interpreter times out for the [1,2,3,4,5,6,7,8,9],4
test case, regardless of outputting the length or the list.
Explanation:
á :Get all permutations
f_ :Keep only ones where:
åÔ : Get the cumulative maximums (i.e. the visible buildings)
â Ê : Count the number of unique items
¥V : True if it's the requested number
add a comment |
up vote
1
down vote
JavaScript (ES6), 108 107 bytes
Takes input as (k)(array)
. Prints the results with alert()
.
k=>P=(a,p=,n=k,h=0)=>a.map((v,i)=>P(a.filter(_=>i--),[...p,v],n-(v>h),v>h?v:h))+a||n||P[p]||alert(P[p]=p)
Try it online!
Commented
k => // k = target number of visible buildings
P = ( // P = recursive function taking:
a, // a = list of building heights
p = , // p = current permutation
n = k, // n = counter initialized to k
h = 0 // h = height of the highest building so far
) => //
a.map((v, i) => // for each value v at position i in a:
P( // do a recursive call:
a.filter(_ => i--), // using a copy of a without the i-th element
[...p, v], // append v to p
n - (v > h), // decrement n if v is greater than h
v > h ? v : h // update h to max(h, v)
) // end of recursive call
) // end of map()
+ a || // unless a was not empty,
n || // or n is not equal to 0,
P[p] || // or p was already printed,
alert(P[p] = p) // print p and store it in P
add a comment |
up vote
0
down vote
Python 2, 114 113 bytes
lambda a,n:{p for p in permutations(a)if-~sum(p[i]>max(p[:i])for i in range(1,len(p)))==n}
from itertools import*
Try it online!
-1 byte, thanks to ovs
Python 3, 113 bytes
lambda a,n:{p for p in permutations(a)if sum(v>max(p[:p.index(v)]+(v-1,))for v in{*p})==n}
from itertools import*
Try it online!
add a comment |
up vote
0
down vote
J, 43 38 bytes
-5 bytes after incorporating an optimization from Kevin's O5AB13 answer
(]#~[=([:#@~.>./)"1@])[:~.i.@!@#@]A.]
Try it online!
ungolfed
(] #~ [ = ([: #@~. >./)"1@]) ([: ~. i.@!@#@] A. ])
explanation
we're merely listing all possible perms i.@!@#@] A. ]
, taking uniq items thereof with ~.
, then filtering those by the number of visible building, which must equal the left input.
the key logic is in the parenthetical verb which calcs the number of visible buildings:
([: #@~. >./)
Here we use a max scan >./
to keep a tally of the tallest building seen so far. Then we just take the unique elements of the max scan, and that's the number of visible buildings.
add a comment |
9 Answers
9
active
oldest
votes
9 Answers
9
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
6
down vote
05AB1E, 10 9 bytes
œÙʒη€àÙgQ
Try it online or verify (almost) all test cases (test case [1,2,3,4,5,6,7,8,9],4
times out).
Footer of the TIO does what OP asked at the bottom:
Optional: If possible, can you add something like
if length is greater than 20: print length else print answer
. In the footer, not in the code.
Explanation:
œ # Permutations of the (implicit) input-list
# i.e. [1,2,2] → [[1,2,2],[1,2,2],[2,1,2],[2,2,1],[2,1,2],[2,2,1]]
Ù # Only leave the unique permutations
# i.e. [[1,2,2],[1,2,2],[2,1,2],[2,2,1],[2,1,2],[2,2,1]]
# → [[1,2,2],[2,1,2],[2,2,1]]
ʒ # Filter it by:
η # Push the prefixes of the current permutation
# i.e. [1,2,2] → [[1],[1,2],[1,2,2]]
ۈ # Calculate the maximum of each permutation
# i.e. [[1],[1,2],[1,2,2]] → [1,2,2]
Ù # Only leave the unique maximums
# i.e. [1,2,2] → [1,2]
g # And take the length
# i.e. [1,2] → 2
Q # And only leave those equal to the second (implicit) input
# i.e. 2 and 2 → 1 (truthy)
1
Impressive, every single byte here is part of the function tree!
– lirtosiast
Nov 15 at 9:23
1
@lirtosiast Yeah, 05AB1E has some pretty short builtins sometimes, which were perfect in this challenge. :) It's actually very similar to your Pyth answer I see. Funny thing is, is that the footer forif length is greater than 20: print length; else print answer;
is a̶ ̶b̶y̶t̶e̶ ̶l̶o̶n̶g̶e̶r̶ of equal length in comparison to the program itself. xD
– Kevin Cruijssen
Nov 15 at 9:25
add a comment |
up vote
6
down vote
05AB1E, 10 9 bytes
œÙʒη€àÙgQ
Try it online or verify (almost) all test cases (test case [1,2,3,4,5,6,7,8,9],4
times out).
Footer of the TIO does what OP asked at the bottom:
Optional: If possible, can you add something like
if length is greater than 20: print length else print answer
. In the footer, not in the code.
Explanation:
œ # Permutations of the (implicit) input-list
# i.e. [1,2,2] → [[1,2,2],[1,2,2],[2,1,2],[2,2,1],[2,1,2],[2,2,1]]
Ù # Only leave the unique permutations
# i.e. [[1,2,2],[1,2,2],[2,1,2],[2,2,1],[2,1,2],[2,2,1]]
# → [[1,2,2],[2,1,2],[2,2,1]]
ʒ # Filter it by:
η # Push the prefixes of the current permutation
# i.e. [1,2,2] → [[1],[1,2],[1,2,2]]
ۈ # Calculate the maximum of each permutation
# i.e. [[1],[1,2],[1,2,2]] → [1,2,2]
Ù # Only leave the unique maximums
# i.e. [1,2,2] → [1,2]
g # And take the length
# i.e. [1,2] → 2
Q # And only leave those equal to the second (implicit) input
# i.e. 2 and 2 → 1 (truthy)
1
Impressive, every single byte here is part of the function tree!
– lirtosiast
Nov 15 at 9:23
1
@lirtosiast Yeah, 05AB1E has some pretty short builtins sometimes, which were perfect in this challenge. :) It's actually very similar to your Pyth answer I see. Funny thing is, is that the footer forif length is greater than 20: print length; else print answer;
is a̶ ̶b̶y̶t̶e̶ ̶l̶o̶n̶g̶e̶r̶ of equal length in comparison to the program itself. xD
– Kevin Cruijssen
Nov 15 at 9:25
add a comment |
up vote
6
down vote
up vote
6
down vote
05AB1E, 10 9 bytes
œÙʒη€àÙgQ
Try it online or verify (almost) all test cases (test case [1,2,3,4,5,6,7,8,9],4
times out).
Footer of the TIO does what OP asked at the bottom:
Optional: If possible, can you add something like
if length is greater than 20: print length else print answer
. In the footer, not in the code.
Explanation:
œ # Permutations of the (implicit) input-list
# i.e. [1,2,2] → [[1,2,2],[1,2,2],[2,1,2],[2,2,1],[2,1,2],[2,2,1]]
Ù # Only leave the unique permutations
# i.e. [[1,2,2],[1,2,2],[2,1,2],[2,2,1],[2,1,2],[2,2,1]]
# → [[1,2,2],[2,1,2],[2,2,1]]
ʒ # Filter it by:
η # Push the prefixes of the current permutation
# i.e. [1,2,2] → [[1],[1,2],[1,2,2]]
ۈ # Calculate the maximum of each permutation
# i.e. [[1],[1,2],[1,2,2]] → [1,2,2]
Ù # Only leave the unique maximums
# i.e. [1,2,2] → [1,2]
g # And take the length
# i.e. [1,2] → 2
Q # And only leave those equal to the second (implicit) input
# i.e. 2 and 2 → 1 (truthy)
05AB1E, 10 9 bytes
œÙʒη€àÙgQ
Try it online or verify (almost) all test cases (test case [1,2,3,4,5,6,7,8,9],4
times out).
Footer of the TIO does what OP asked at the bottom:
Optional: If possible, can you add something like
if length is greater than 20: print length else print answer
. In the footer, not in the code.
Explanation:
œ # Permutations of the (implicit) input-list
# i.e. [1,2,2] → [[1,2,2],[1,2,2],[2,1,2],[2,2,1],[2,1,2],[2,2,1]]
Ù # Only leave the unique permutations
# i.e. [[1,2,2],[1,2,2],[2,1,2],[2,2,1],[2,1,2],[2,2,1]]
# → [[1,2,2],[2,1,2],[2,2,1]]
ʒ # Filter it by:
η # Push the prefixes of the current permutation
# i.e. [1,2,2] → [[1],[1,2],[1,2,2]]
ۈ # Calculate the maximum of each permutation
# i.e. [[1],[1,2],[1,2,2]] → [1,2,2]
Ù # Only leave the unique maximums
# i.e. [1,2,2] → [1,2]
g # And take the length
# i.e. [1,2] → 2
Q # And only leave those equal to the second (implicit) input
# i.e. 2 and 2 → 1 (truthy)
edited Nov 15 at 9:27
answered Nov 15 at 9:15
Kevin Cruijssen
34.2k554181
34.2k554181
1
Impressive, every single byte here is part of the function tree!
– lirtosiast
Nov 15 at 9:23
1
@lirtosiast Yeah, 05AB1E has some pretty short builtins sometimes, which were perfect in this challenge. :) It's actually very similar to your Pyth answer I see. Funny thing is, is that the footer forif length is greater than 20: print length; else print answer;
is a̶ ̶b̶y̶t̶e̶ ̶l̶o̶n̶g̶e̶r̶ of equal length in comparison to the program itself. xD
– Kevin Cruijssen
Nov 15 at 9:25
add a comment |
1
Impressive, every single byte here is part of the function tree!
– lirtosiast
Nov 15 at 9:23
1
@lirtosiast Yeah, 05AB1E has some pretty short builtins sometimes, which were perfect in this challenge. :) It's actually very similar to your Pyth answer I see. Funny thing is, is that the footer forif length is greater than 20: print length; else print answer;
is a̶ ̶b̶y̶t̶e̶ ̶l̶o̶n̶g̶e̶r̶ of equal length in comparison to the program itself. xD
– Kevin Cruijssen
Nov 15 at 9:25
1
1
Impressive, every single byte here is part of the function tree!
– lirtosiast
Nov 15 at 9:23
Impressive, every single byte here is part of the function tree!
– lirtosiast
Nov 15 at 9:23
1
1
@lirtosiast Yeah, 05AB1E has some pretty short builtins sometimes, which were perfect in this challenge. :) It's actually very similar to your Pyth answer I see. Funny thing is, is that the footer for
if length is greater than 20: print length; else print answer;
is a̶ ̶b̶y̶t̶e̶ ̶l̶o̶n̶g̶e̶r̶ of equal length in comparison to the program itself. xD– Kevin Cruijssen
Nov 15 at 9:25
@lirtosiast Yeah, 05AB1E has some pretty short builtins sometimes, which were perfect in this challenge. :) It's actually very similar to your Pyth answer I see. Funny thing is, is that the footer for
if length is greater than 20: print length; else print answer;
is a̶ ̶b̶y̶t̶e̶ ̶l̶o̶n̶g̶e̶r̶ of equal length in comparison to the program itself. xD– Kevin Cruijssen
Nov 15 at 9:25
add a comment |
up vote
5
down vote
Haskell, 73 bytes
import Data.List
f n=filter((n==).length.nub.scanl1 max).nub.permutations
Try it online!
add a comment |
up vote
5
down vote
Haskell, 73 bytes
import Data.List
f n=filter((n==).length.nub.scanl1 max).nub.permutations
Try it online!
add a comment |
up vote
5
down vote
up vote
5
down vote
Haskell, 73 bytes
import Data.List
f n=filter((n==).length.nub.scanl1 max).nub.permutations
Try it online!
Haskell, 73 bytes
import Data.List
f n=filter((n==).length.nub.scanl1 max).nub.permutations
Try it online!
answered Nov 15 at 7:35
nimi
30.8k31985
30.8k31985
add a comment |
add a comment |
up vote
5
down vote
Jelly, 12 10 bytes
Œ!Q»QL=ʋƇ
Try it online!
-2 bytes by @Erik the Outgolfer
This is a dyadic function taking the building heights and k
in that order.
Œ! All permutations of first input
Œ!Q Unique permutations of first input
» Running maximum
Q Unique values
L Length of this array
= Equals k
ʋ Create a monad from these 4 links
»QL=ʋ "Are exactly k buildings visible in arrangement x?"
Ƈ Filter if f(x)
Œ!Q»QL=ʋƇ All distinct perms of first input with k visible buildings.
1
Hail the newʋ
! (it's pretty older thanƇ
, actually :P)
– Erik the Outgolfer
Nov 15 at 12:36
add a comment |
up vote
5
down vote
Jelly, 12 10 bytes
Œ!Q»QL=ʋƇ
Try it online!
-2 bytes by @Erik the Outgolfer
This is a dyadic function taking the building heights and k
in that order.
Œ! All permutations of first input
Œ!Q Unique permutations of first input
» Running maximum
Q Unique values
L Length of this array
= Equals k
ʋ Create a monad from these 4 links
»QL=ʋ "Are exactly k buildings visible in arrangement x?"
Ƈ Filter if f(x)
Œ!Q»QL=ʋƇ All distinct perms of first input with k visible buildings.
1
Hail the newʋ
! (it's pretty older thanƇ
, actually :P)
– Erik the Outgolfer
Nov 15 at 12:36
add a comment |
up vote
5
down vote
up vote
5
down vote
Jelly, 12 10 bytes
Œ!Q»QL=ʋƇ
Try it online!
-2 bytes by @Erik the Outgolfer
This is a dyadic function taking the building heights and k
in that order.
Œ! All permutations of first input
Œ!Q Unique permutations of first input
» Running maximum
Q Unique values
L Length of this array
= Equals k
ʋ Create a monad from these 4 links
»QL=ʋ "Are exactly k buildings visible in arrangement x?"
Ƈ Filter if f(x)
Œ!Q»QL=ʋƇ All distinct perms of first input with k visible buildings.
Jelly, 12 10 bytes
Œ!Q»QL=ʋƇ
Try it online!
-2 bytes by @Erik the Outgolfer
This is a dyadic function taking the building heights and k
in that order.
Œ! All permutations of first input
Œ!Q Unique permutations of first input
» Running maximum
Q Unique values
L Length of this array
= Equals k
ʋ Create a monad from these 4 links
»QL=ʋ "Are exactly k buildings visible in arrangement x?"
Ƈ Filter if f(x)
Œ!Q»QL=ʋƇ All distinct perms of first input with k visible buildings.
edited Nov 15 at 13:16
answered Nov 15 at 8:39
lirtosiast
15.5k436104
15.5k436104
1
Hail the newʋ
! (it's pretty older thanƇ
, actually :P)
– Erik the Outgolfer
Nov 15 at 12:36
add a comment |
1
Hail the newʋ
! (it's pretty older thanƇ
, actually :P)
– Erik the Outgolfer
Nov 15 at 12:36
1
1
Hail the new
ʋ
! (it's pretty older than Ƈ
, actually :P)– Erik the Outgolfer
Nov 15 at 12:36
Hail the new
ʋ
! (it's pretty older than Ƈ
, actually :P)– Erik the Outgolfer
Nov 15 at 12:36
add a comment |
up vote
4
down vote
Pyth, 18 16 bytes
fqvzl{meSd._T{.p
Try it here.
Note that the online version of the Pyth interpreter throws a memory error on the largest test case.
f Filter lambda T:
q Are second input and # visible buildings equal?
v z The second input value
l { The number of unique elements in
m the maximums
e S d ...
._ T of prefixes of T
{ .p over unique permutations of (implicit first input)
Welcome back! :-)
– Luis Mendo
Nov 15 at 12:49
add a comment |
up vote
4
down vote
Pyth, 18 16 bytes
fqvzl{meSd._T{.p
Try it here.
Note that the online version of the Pyth interpreter throws a memory error on the largest test case.
f Filter lambda T:
q Are second input and # visible buildings equal?
v z The second input value
l { The number of unique elements in
m the maximums
e S d ...
._ T of prefixes of T
{ .p over unique permutations of (implicit first input)
Welcome back! :-)
– Luis Mendo
Nov 15 at 12:49
add a comment |
up vote
4
down vote
up vote
4
down vote
Pyth, 18 16 bytes
fqvzl{meSd._T{.p
Try it here.
Note that the online version of the Pyth interpreter throws a memory error on the largest test case.
f Filter lambda T:
q Are second input and # visible buildings equal?
v z The second input value
l { The number of unique elements in
m the maximums
e S d ...
._ T of prefixes of T
{ .p over unique permutations of (implicit first input)
Pyth, 18 16 bytes
fqvzl{meSd._T{.p
Try it here.
Note that the online version of the Pyth interpreter throws a memory error on the largest test case.
f Filter lambda T:
q Are second input and # visible buildings equal?
v z The second input value
l { The number of unique elements in
m the maximums
e S d ...
._ T of prefixes of T
{ .p over unique permutations of (implicit first input)
edited Nov 15 at 9:01
answered Nov 15 at 6:58
lirtosiast
15.5k436104
15.5k436104
Welcome back! :-)
– Luis Mendo
Nov 15 at 12:49
add a comment |
Welcome back! :-)
– Luis Mendo
Nov 15 at 12:49
Welcome back! :-)
– Luis Mendo
Nov 15 at 12:49
Welcome back! :-)
– Luis Mendo
Nov 15 at 12:49
add a comment |
up vote
2
down vote
Perl 6, 81 63 bytes
-18 bytes thanks to nwellnhof!
{;*.permutations.unique(:with(*eqv*)).grep:{$_==set [max] @_}}
Try it online!
Anonymous code block that takes input curried, e.g. f(n)(list)
. That .unique(:with(*eqv*))
is annoyingly long though :(
Explanation:
{; } # Anonymous code block
*.permutations.unique(:with(*eqv*)) # From all distinct permutations
.grep:{ } # Filter where
set [max] @_ # Visible buildings
$_== # Equals num
1
FWIW, I just filed a Rakudo issue so we might get rid of that annoying;
eventually ;)
– nwellnhof
Nov 15 at 9:55
add a comment |
up vote
2
down vote
Perl 6, 81 63 bytes
-18 bytes thanks to nwellnhof!
{;*.permutations.unique(:with(*eqv*)).grep:{$_==set [max] @_}}
Try it online!
Anonymous code block that takes input curried, e.g. f(n)(list)
. That .unique(:with(*eqv*))
is annoyingly long though :(
Explanation:
{; } # Anonymous code block
*.permutations.unique(:with(*eqv*)) # From all distinct permutations
.grep:{ } # Filter where
set [max] @_ # Visible buildings
$_== # Equals num
1
FWIW, I just filed a Rakudo issue so we might get rid of that annoying;
eventually ;)
– nwellnhof
Nov 15 at 9:55
add a comment |
up vote
2
down vote
up vote
2
down vote
Perl 6, 81 63 bytes
-18 bytes thanks to nwellnhof!
{;*.permutations.unique(:with(*eqv*)).grep:{$_==set [max] @_}}
Try it online!
Anonymous code block that takes input curried, e.g. f(n)(list)
. That .unique(:with(*eqv*))
is annoyingly long though :(
Explanation:
{; } # Anonymous code block
*.permutations.unique(:with(*eqv*)) # From all distinct permutations
.grep:{ } # Filter where
set [max] @_ # Visible buildings
$_== # Equals num
Perl 6, 81 63 bytes
-18 bytes thanks to nwellnhof!
{;*.permutations.unique(:with(*eqv*)).grep:{$_==set [max] @_}}
Try it online!
Anonymous code block that takes input curried, e.g. f(n)(list)
. That .unique(:with(*eqv*))
is annoyingly long though :(
Explanation:
{; } # Anonymous code block
*.permutations.unique(:with(*eqv*)) # From all distinct permutations
.grep:{ } # Filter where
set [max] @_ # Visible buildings
$_== # Equals num
edited Nov 15 at 9:49
answered Nov 15 at 7:04
Jo King
19.2k245102
19.2k245102
1
FWIW, I just filed a Rakudo issue so we might get rid of that annoying;
eventually ;)
– nwellnhof
Nov 15 at 9:55
add a comment |
1
FWIW, I just filed a Rakudo issue so we might get rid of that annoying;
eventually ;)
– nwellnhof
Nov 15 at 9:55
1
1
FWIW, I just filed a Rakudo issue so we might get rid of that annoying
;
eventually ;)– nwellnhof
Nov 15 at 9:55
FWIW, I just filed a Rakudo issue so we might get rid of that annoying
;
eventually ;)– nwellnhof
Nov 15 at 9:55
add a comment |
up vote
2
down vote
Japt, 11 bytes
á f_åÔâ Ê¥V
Try it online!
For the longer outputs, adding } l
to the end will output the length instead. The online interpreter times out for the [1,2,3,4,5,6,7,8,9],4
test case, regardless of outputting the length or the list.
Explanation:
á :Get all permutations
f_ :Keep only ones where:
åÔ : Get the cumulative maximums (i.e. the visible buildings)
â Ê : Count the number of unique items
¥V : True if it's the requested number
add a comment |
up vote
2
down vote
Japt, 11 bytes
á f_åÔâ Ê¥V
Try it online!
For the longer outputs, adding } l
to the end will output the length instead. The online interpreter times out for the [1,2,3,4,5,6,7,8,9],4
test case, regardless of outputting the length or the list.
Explanation:
á :Get all permutations
f_ :Keep only ones where:
åÔ : Get the cumulative maximums (i.e. the visible buildings)
â Ê : Count the number of unique items
¥V : True if it's the requested number
add a comment |
up vote
2
down vote
up vote
2
down vote
Japt, 11 bytes
á f_åÔâ Ê¥V
Try it online!
For the longer outputs, adding } l
to the end will output the length instead. The online interpreter times out for the [1,2,3,4,5,6,7,8,9],4
test case, regardless of outputting the length or the list.
Explanation:
á :Get all permutations
f_ :Keep only ones where:
åÔ : Get the cumulative maximums (i.e. the visible buildings)
â Ê : Count the number of unique items
¥V : True if it's the requested number
Japt, 11 bytes
á f_åÔâ Ê¥V
Try it online!
For the longer outputs, adding } l
to the end will output the length instead. The online interpreter times out for the [1,2,3,4,5,6,7,8,9],4
test case, regardless of outputting the length or the list.
Explanation:
á :Get all permutations
f_ :Keep only ones where:
åÔ : Get the cumulative maximums (i.e. the visible buildings)
â Ê : Count the number of unique items
¥V : True if it's the requested number
answered Nov 15 at 15:27
Kamil Drakari
2,551416
2,551416
add a comment |
add a comment |
up vote
1
down vote
JavaScript (ES6), 108 107 bytes
Takes input as (k)(array)
. Prints the results with alert()
.
k=>P=(a,p=,n=k,h=0)=>a.map((v,i)=>P(a.filter(_=>i--),[...p,v],n-(v>h),v>h?v:h))+a||n||P[p]||alert(P[p]=p)
Try it online!
Commented
k => // k = target number of visible buildings
P = ( // P = recursive function taking:
a, // a = list of building heights
p = , // p = current permutation
n = k, // n = counter initialized to k
h = 0 // h = height of the highest building so far
) => //
a.map((v, i) => // for each value v at position i in a:
P( // do a recursive call:
a.filter(_ => i--), // using a copy of a without the i-th element
[...p, v], // append v to p
n - (v > h), // decrement n if v is greater than h
v > h ? v : h // update h to max(h, v)
) // end of recursive call
) // end of map()
+ a || // unless a was not empty,
n || // or n is not equal to 0,
P[p] || // or p was already printed,
alert(P[p] = p) // print p and store it in P
add a comment |
up vote
1
down vote
JavaScript (ES6), 108 107 bytes
Takes input as (k)(array)
. Prints the results with alert()
.
k=>P=(a,p=,n=k,h=0)=>a.map((v,i)=>P(a.filter(_=>i--),[...p,v],n-(v>h),v>h?v:h))+a||n||P[p]||alert(P[p]=p)
Try it online!
Commented
k => // k = target number of visible buildings
P = ( // P = recursive function taking:
a, // a = list of building heights
p = , // p = current permutation
n = k, // n = counter initialized to k
h = 0 // h = height of the highest building so far
) => //
a.map((v, i) => // for each value v at position i in a:
P( // do a recursive call:
a.filter(_ => i--), // using a copy of a without the i-th element
[...p, v], // append v to p
n - (v > h), // decrement n if v is greater than h
v > h ? v : h // update h to max(h, v)
) // end of recursive call
) // end of map()
+ a || // unless a was not empty,
n || // or n is not equal to 0,
P[p] || // or p was already printed,
alert(P[p] = p) // print p and store it in P
add a comment |
up vote
1
down vote
up vote
1
down vote
JavaScript (ES6), 108 107 bytes
Takes input as (k)(array)
. Prints the results with alert()
.
k=>P=(a,p=,n=k,h=0)=>a.map((v,i)=>P(a.filter(_=>i--),[...p,v],n-(v>h),v>h?v:h))+a||n||P[p]||alert(P[p]=p)
Try it online!
Commented
k => // k = target number of visible buildings
P = ( // P = recursive function taking:
a, // a = list of building heights
p = , // p = current permutation
n = k, // n = counter initialized to k
h = 0 // h = height of the highest building so far
) => //
a.map((v, i) => // for each value v at position i in a:
P( // do a recursive call:
a.filter(_ => i--), // using a copy of a without the i-th element
[...p, v], // append v to p
n - (v > h), // decrement n if v is greater than h
v > h ? v : h // update h to max(h, v)
) // end of recursive call
) // end of map()
+ a || // unless a was not empty,
n || // or n is not equal to 0,
P[p] || // or p was already printed,
alert(P[p] = p) // print p and store it in P
JavaScript (ES6), 108 107 bytes
Takes input as (k)(array)
. Prints the results with alert()
.
k=>P=(a,p=,n=k,h=0)=>a.map((v,i)=>P(a.filter(_=>i--),[...p,v],n-(v>h),v>h?v:h))+a||n||P[p]||alert(P[p]=p)
Try it online!
Commented
k => // k = target number of visible buildings
P = ( // P = recursive function taking:
a, // a = list of building heights
p = , // p = current permutation
n = k, // n = counter initialized to k
h = 0 // h = height of the highest building so far
) => //
a.map((v, i) => // for each value v at position i in a:
P( // do a recursive call:
a.filter(_ => i--), // using a copy of a without the i-th element
[...p, v], // append v to p
n - (v > h), // decrement n if v is greater than h
v > h ? v : h // update h to max(h, v)
) // end of recursive call
) // end of map()
+ a || // unless a was not empty,
n || // or n is not equal to 0,
P[p] || // or p was already printed,
alert(P[p] = p) // print p and store it in P
edited Nov 15 at 10:46
answered Nov 15 at 10:04
Arnauld
69.2k585293
69.2k585293
add a comment |
add a comment |
up vote
0
down vote
Python 2, 114 113 bytes
lambda a,n:{p for p in permutations(a)if-~sum(p[i]>max(p[:i])for i in range(1,len(p)))==n}
from itertools import*
Try it online!
-1 byte, thanks to ovs
Python 3, 113 bytes
lambda a,n:{p for p in permutations(a)if sum(v>max(p[:p.index(v)]+(v-1,))for v in{*p})==n}
from itertools import*
Try it online!
add a comment |
up vote
0
down vote
Python 2, 114 113 bytes
lambda a,n:{p for p in permutations(a)if-~sum(p[i]>max(p[:i])for i in range(1,len(p)))==n}
from itertools import*
Try it online!
-1 byte, thanks to ovs
Python 3, 113 bytes
lambda a,n:{p for p in permutations(a)if sum(v>max(p[:p.index(v)]+(v-1,))for v in{*p})==n}
from itertools import*
Try it online!
add a comment |
up vote
0
down vote
up vote
0
down vote
Python 2, 114 113 bytes
lambda a,n:{p for p in permutations(a)if-~sum(p[i]>max(p[:i])for i in range(1,len(p)))==n}
from itertools import*
Try it online!
-1 byte, thanks to ovs
Python 3, 113 bytes
lambda a,n:{p for p in permutations(a)if sum(v>max(p[:p.index(v)]+(v-1,))for v in{*p})==n}
from itertools import*
Try it online!
Python 2, 114 113 bytes
lambda a,n:{p for p in permutations(a)if-~sum(p[i]>max(p[:i])for i in range(1,len(p)))==n}
from itertools import*
Try it online!
-1 byte, thanks to ovs
Python 3, 113 bytes
lambda a,n:{p for p in permutations(a)if sum(v>max(p[:p.index(v)]+(v-1,))for v in{*p})==n}
from itertools import*
Try it online!
edited Nov 15 at 10:22
answered Nov 15 at 7:57
TFeld
13.5k21139
13.5k21139
add a comment |
add a comment |
up vote
0
down vote
J, 43 38 bytes
-5 bytes after incorporating an optimization from Kevin's O5AB13 answer
(]#~[=([:#@~.>./)"1@])[:~.i.@!@#@]A.]
Try it online!
ungolfed
(] #~ [ = ([: #@~. >./)"1@]) ([: ~. i.@!@#@] A. ])
explanation
we're merely listing all possible perms i.@!@#@] A. ]
, taking uniq items thereof with ~.
, then filtering those by the number of visible building, which must equal the left input.
the key logic is in the parenthetical verb which calcs the number of visible buildings:
([: #@~. >./)
Here we use a max scan >./
to keep a tally of the tallest building seen so far. Then we just take the unique elements of the max scan, and that's the number of visible buildings.
add a comment |
up vote
0
down vote
J, 43 38 bytes
-5 bytes after incorporating an optimization from Kevin's O5AB13 answer
(]#~[=([:#@~.>./)"1@])[:~.i.@!@#@]A.]
Try it online!
ungolfed
(] #~ [ = ([: #@~. >./)"1@]) ([: ~. i.@!@#@] A. ])
explanation
we're merely listing all possible perms i.@!@#@] A. ]
, taking uniq items thereof with ~.
, then filtering those by the number of visible building, which must equal the left input.
the key logic is in the parenthetical verb which calcs the number of visible buildings:
([: #@~. >./)
Here we use a max scan >./
to keep a tally of the tallest building seen so far. Then we just take the unique elements of the max scan, and that's the number of visible buildings.
add a comment |
up vote
0
down vote
up vote
0
down vote
J, 43 38 bytes
-5 bytes after incorporating an optimization from Kevin's O5AB13 answer
(]#~[=([:#@~.>./)"1@])[:~.i.@!@#@]A.]
Try it online!
ungolfed
(] #~ [ = ([: #@~. >./)"1@]) ([: ~. i.@!@#@] A. ])
explanation
we're merely listing all possible perms i.@!@#@] A. ]
, taking uniq items thereof with ~.
, then filtering those by the number of visible building, which must equal the left input.
the key logic is in the parenthetical verb which calcs the number of visible buildings:
([: #@~. >./)
Here we use a max scan >./
to keep a tally of the tallest building seen so far. Then we just take the unique elements of the max scan, and that's the number of visible buildings.
J, 43 38 bytes
-5 bytes after incorporating an optimization from Kevin's O5AB13 answer
(]#~[=([:#@~.>./)"1@])[:~.i.@!@#@]A.]
Try it online!
ungolfed
(] #~ [ = ([: #@~. >./)"1@]) ([: ~. i.@!@#@] A. ])
explanation
we're merely listing all possible perms i.@!@#@] A. ]
, taking uniq items thereof with ~.
, then filtering those by the number of visible building, which must equal the left input.
the key logic is in the parenthetical verb which calcs the number of visible buildings:
([: #@~. >./)
Here we use a max scan >./
to keep a tally of the tallest building seen so far. Then we just take the unique elements of the max scan, and that's the number of visible buildings.
edited Nov 17 at 5:49
answered Nov 17 at 5:21
Jonah
1,951816
1,951816
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f175970%2fhide-the-buildings%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Should the output be all qualifying permutations, or the number thereof?
– Luis Mendo
Nov 15 at 6:49
It should be all qualifying permutations @LuisMendo
– Vedant Kandoi
Nov 15 at 6:54
Suggested test case:
[1,2,3,4,5],5 -> [(1,2,3,4,5)]
. None of the current test cases ensure that answers can support showing all buildings (though I don't know whether any actually have a problem with that).– Kamil Drakari
Nov 15 at 15:27