title: Bridges and Tunnels

text:
# Question
Title: Bridges and Tunnels
You are responsible for building a new freeway. However, it leads through mountainous lands and therefore needs numerous bridges and tunnels. The freeway itself should stay at a single level.

**Input**

You are given a rough ASCII description of how the mountains look like on standard input, such as the following:

```
                         /\
                        /  \
                   /\  /    \
            /\    /  \/      \
           /  \  /            \                  /\
          /    \/              \                /  \
_        /                      \        /\    /    \
 \      /                        \      /  \  /      \  /\
  \    /                          \    /    \/        \/  \
   \  /                            \  /
    \/                              \/

```

The `_` in the first column marks the beginning and the level of the road. The mountain range is contiguous and if the last segment will be a bridge, it has an even number of characters.

You may assume that a line of input is never longer than 100 characters and that there are no more than 15 lines. Every line has the same length which is possibly space-padded at the end. The road never starts within a mountain or as a bridge. The first thing following the road tile in the input is either a slope down or up.

**Output**

Output is the same mountain range, except that there is now a road where previously was only its beginning. Output is given on standard output.

For this there are numerous rules:

1. The road must start at the place indicated in the input and remain the same level throughout. To make it easier, we have prepared a number of premade road tiles which look like this: `_`:

```
_______
 \    /
  \/\/

```
2. The road must extend to the far end of the mountain range (i.e. the length of the input lines dictates how far the road goes).
3. Tunnels must be drilled whenever a mountain is where the road needs to go. Tunnels go straight through the mountain and leave holes at the start and the end (i.e. a tunnel replaces the slope of the mountain with a closing parenthesis at its start and an opening parenthesis at its end).
4. Tunnels leave, well, a tunnel in the mountain which usually has a ceiling. Our premade road tiles luckily can be used to reinforce the ceiling so that the tunnel does not collapse (the line above the tunnel has to use `_` to reinforce the tunnel):

```
      /\
     /  \
    /____\
___)______(__
 \/        \/

```
5. The tunnel does not need to be reinforced when the mountain isn't high enough above it. It sounds weird to me as well but I have been told the premade road tiles are strong enough to hold even when spaced out in that case (no tunnel ceiling is drawn when there is a slope directly above the tunnel):

```
       /\
    /\/__\
___)______(__
 \/        \/

```
6. Bridges are needed whenever the road needs to cross a chasm. For short bridges the premade road tiles are strong enough but still need a bit support at the beginning and end of the bridge (the first downward slope under the bridge and the last upward slope are replaced by `Y` so that there is a support beam for the bridge):

```
_____
 Y  Y
  \/

```
7. Longer bridges need additional support. A long bridge is one that has more than six unsupported road tiles in a row. Long bridges need a pillar in their center. Pillars are easily built with our prebuilt pillar beams which look like this: `|`. Each pillar needs two of those and they extend down to the bottom of the chasm:

```
_____________________________
 Y            ||            Y
  \        /\ || /\      /\/
   \  /\  /  \||/  \  /\/
    \/  \/    \/    \/

```
8. Since the input only represents a portion of the whole mountain range the freeway needs to be built through, it may end abruptly in the middle of a bridge or tunnel. The long bridge rule still applies for the final segment and you can assume that the first part beyond the given input supports the bridge again.

Following the above rules we get the following for our input:

```
                         /\
                        /  \
                   /\  /    \
            /\    /  \/      \
           /  \  /            \                  /\
          /____\/______________\                /__\
_________)______________________(________)(____)____(______
 Y      Y                        Y      Y  Y  Y      Y  YY
  \    /                          \    /    \/        \/  \
   \  /                            \  /
    \/                              \/

```

Shortest code by character count wins. Trailing whitespace in the lines is ignored for validation.

**Sample input 1**

```
_
 \                            /\
  \                          /  \
   \                        /    \
    \                /\    /      \              /\        /
     \    /\        /  \  /        \      /\  /\/  \      /
      \  /  \      /    \/          \    /  \/      \/\  /
       \/    \    /                  \  /              \/
              \  /                    \/
               \/

```

**Sample output 1**

```
____________________________________________________________
 Y             ||             YY             ||
  \            ||            /  \            ||
   \           ||           /    \           ||
    \          ||    /\    /      \          ||  /\        /
     \    /\   ||   /  \  /        \      /\ |/\/  \      /
      \  /  \  ||  /    \/          \    /  \/      \/\  /
       \/    \ || /                  \  /              \/
              \||/                    \/
               \/

```

**Sample input 2**

```
                                           /\  /\
                                          /  \/  \                    /
           /\                            /        \  /\              /
    /\    /  \                          /          \/  \            /
   /  \  /    \/\                      /                \    /\    /
  /    \/        \                    /                  \  /  \  /
_/                \                  /                    \/    \/
                   \                /
                    \            /\/
                     \  /\      /
                      \/  \    /
                           \  /
                            \/

```

**Sample output 2**

```
                                           /\  /\
                                          /  \/  \                    /
           /\                            /        \  /\              /
    /\    /  \                          /          \/  \            /
   /  \  /    \/\                      /                \    /\    /
  /____\/________\                    /__________________\  /__\  /____
_)________________(__________________)____________________()____()_____
                   Y       ||       Y
                    \      ||    /\/
                     \  /\ ||   /
                      \/  \||  /
                           \| /
                            \/

```

**Note**

Trailing spaces in the output are ignored for comparison with the reference solutions.

**Winning condition**

Shortest code wins, as is customary in golf. In case of a tie, the earlier solution wins.

**Test cases**

There are two tests scripts, containing identical test cases:

Invocation is in both cases: `<test script> <my program> [arguments]`, e.g. `./test ruby bridges.rb` or `./test.ps1 ./bridges.exe`.

**Another note**

This task was part of a golf contest held at my university during 2011-W24. The scores and languages of our contestants were as follows:

* 304 – Perl
* 343 – C
* 375 – C
* 648 – Python

Our own solution (thanks to Ventero) was

* 262 – Ruby

# Answer
## Perl, 210 195 194 193 chars

*update*

Same ideas, but applied very differently, for the most part.

Run with `perl -p0` (4 chars counted for the switches).

```
($o,$c,$r,$b)=/((.+\n)?(_.+\n)(.+\n)?)/;/\n/;$n=$-[0];$c=~s{/ }{/_}g;$r=~y{ /\\}{_)(};map{s{\\(   +)  \1(/|\n)}{\\$1||$1$2}g,y{\\/}{Y}}$b;s/\Q$o/$c$r$b/;1while(s/_ /__/||s/(\|.{$n}) /$1|/s)

```

This also requires a change to the bash test script, so as not to over-quote the args:

```
-   got=$("$cmd" "$args")
+   got=$("$cmd" $args)

```

BTW, I really appreciate the test scripts, @Joey.

commented:

```
#-p : implicitly read input and print after transformations
#-0 : "slurp mode": don't break lines

# grab the roadway line, along with the lines above and below for ceiling and buttresses
# also grab the whole match in $o for replacing later
($o,$c,$r,$b)=/((.+\n)?(_.+\n)(.+\n)?)/;

# compute line length
/\n/;$n=$-[0];

# start ceilings
$c=~s{/ }{/_}g;

# build the road and tunnels
$r=~y{ /\\}{_)(};

# use map to avoid repeating $b =~
map{
  # insert the pillar tops
  s{\\(   +)  \1(/|\n)}{\\$1||$1$2}g,
  # and the buttresses
  y{\\/}{Y}
} $b;

# put those 3 (or 2) lines back into the original
s/\Q$o/$c$r$b/;

# extend ceiling tiles to the right and pillars downward
1while(s/_ /__/||s/(\|.{$n}) /$1|/s)

```

*edits*:

* replace "`{3,}`" with 3 literal spaces and the `+` quantifier, to save another character
* use the `1while(...)` form, where I can omit the semicolon at the end of the script

---

*original* (see history for commented version)

```
@a=map{($r=$n),y{ /\\}{_)(}if/_/;$n++;$_}<>;if($r){while($a[$r-1]=~s{(/[ _]*) }{$1_}){}}map{s{(^|\\)( {3,})  \2(/|$)}{$1$2||$2$3}g;y{\\/}{YY}}$a[$r+1];$_=join'',@a;/\n/;$n=$-[0];while(s/(\|.{$n}) /$1|/s){}print

```

I deliberately didn't look at @Howard's Perl solution until mine was working, but I was able to improve my golfing by looking afterward.

In particular, the regexps for tunnel ceilings and extending pillars helped. Nicely done, Howard.

Conversely, my alternative for getting line length, using the implicit $\_ for the print, leaving off the final semicolon, and removing newlines could shorten Howard's to 222 characters.
> 8 votes

# Answer
### Perl, 234 characters

```
$_=join'',<>;$l=index($_,"\n");
($w)=/(_[^\n]*)/;$w=~y/ \\\//_()/;s/_[^\n]*/$w/e;
while(s/(\/[ _]*) (?=[^\n]*\n_)/$1_/||s/(_.{$l})[\\\/]/$1Y/s){}while(s/(\n( |Y *Y)*)Y( {3,})  \3(Y| ?\n)/\1Y\3||\3\4/||s/(?<=\|.{$l}) /|/s){}
print $_;

```

This is a perl regex-only solution. It passes all given test cases.

The identical but more readable version shows the steps taken to obtain the result:

```
$_=join'',<>;                    # read the input
$l=index($_,"\n");               # determine length of line

($w)=/(_[^\n]*)/;                # extract the line starting with _
$w=~y/ \\\//_()/;                # and build road there (i.e. replace all chars in line)
s/_[^\n]*/$w/e;                  # put road back into string

while(s/(\/[ _]*) (?=[^\n]*\n_)/$1_/||s/(_.{$l})[\\\/]/$1Y/s){}
                                 # build ceiling of tunnels
                                 # build Y supports directly below the road

while(s/(\n( |Y *Y)*)Y( {3,})  \3(Y| ?\n)/\1Y\3||\3\4/||s/(?<=\|.{$l}) /|/s){}
                                 # build center support in middle of bridges
                                 # and extend them down to the ground

print $_;                        # print result

```
> 6 votes

# Answer
# C++, 662 622 598 chars, 4 lines

```
#include<iostream>
#include<string>
#define s for(
#define v g[t][f]
int t,f,r,q,m=-1,w,b,e,h,j,x,y,l,c=18;int main(){std::string g[19];s;r<19;h=c)getline(std::cin,g[r++]);s;c>=0;g[c--].push_back(0))(q=g[c].size())&&g[c][0]-95?0:r=c;s;c<q;y=0){x=g[r][++c];x==47?x=41,w=e=1:++y;x==92?x=40,w=0:++y;t=r-1;f=c;y>1?x=95,w?r&&v==32?v=95:0:++b:0;c-q?0:e=1;t++;s v=x;m<0;)g[h].find(47)<g[h--].npos?m=h:0;t=r+1;if(r<m){(y=v)==47?y=89,e=1:0;v=y-92?y:89;if(e){y=e=0;if((b/=2)>4){j=l=r+1;s;!y;t=j,f=c-b+1,v==32?v=124,++j:0)t=l,y=f=c-b,v==32?v=124,l++,y=0:0;}b=0;}}}s f=q,t=0;t<=m;std::cout<<g[t++]<<'\n')v=32;}

```

This should be it, I've tested this out with the powershell script so it should be ok...

**Edit 1**

Replaced all char constants with numbers, removed successive calls to std::cout + a few other minor changes.

**Edit 2**

last edit, just to get it less than 600. Took out g\[t\]\[f\] as a #define and moved a few things around.
> 4 votes

# Answer
## Ruby, 382 356 353 characters

I thought to give a non-regex solution a shot.

```
m=$<.read;n,r,s,$e,t=(/\n/=~m)+1,/^_/=~m,m.size,(u,d=47,92),0;def j y;$e.member? y;end;(n-1).times{|i|x=r+i;c=m[x];j(c)||(m[x]=95;a,b=x-n,x+n;t<41||a<0||m[a]>32||m[a]=95;b>s||!j(m[b])||(m[b]<d||(p=(/\/|\n/=~m[b..s])/2+b;p-b<4||(w=[f=false,f];p.step(s,n){|p|2.times{|i|(w[i]||=j m[i=p+i])||m[i]='|'}}));m[b]='Y'));c!=u||t=m[x]=41;c!=d||t=m[x]=40};print m

```

The biggest space saver here is to use conditional `||` operator instead of `if - elsif - end`. So instead of writing `if(a) lorem_ipsum end` I've written `!a||lopem_ipsum`. Larger blocks can included using parenthesis `!a||(block)`. If the condition includes `&&` operators then they must negated by using parenthesis and a `!` or by using De Morgan's laws.

And here's the same with more words

```
# read the STDIN to string
mountains = $<.read
line_length,road_level,size,$slopes,in_tunnel =
        (/\n/ =~ mountains) + 1, # Fint the first new line
        /^_/ =~ mountains, # Find the index of the road
        mountains.size,
        (slope_up,slope_down=47,92),
        0

def is_slope y;$slopes.member? y;end

# For each index in the road line
(line_length - 1).times { |i|
  curindex = road_level + i
  curchar = mountains[curindex]

  # If not a slope then
  (is_slope(curchar))|| (

    # mark road as underscore
    mountains[curindex] = 95
    above, below = curindex - line_length, curindex + line_length

    # add roof to tunnel if in tunnel and the mountain
    # is high enough
    in_tunnel<41||above<0||mountains[above]>32||mountains[above]=95

    # If there's a slope character below the road
    below>size||!is_slope(mountains[below])||(

      # if there's a downward slop - start a bridge
      mountains[below]<slope_down||(

          # If bridge is longer than 6 characters
          # Add support to the middle
          support_pos = (/\/|\n/=~mountains[below..size])/2+below
          support_pos-below<4||(
            # Init collision detection
            collision_detected=[f=false,f]
            # Build supports as long as
            # There is mountains below
            support_pos.step(size,line_length) { |support_pos|

               # Add two parallel suppports
               2.times { |i|

               # Add support if the bottom of the
               # gap has not been reached
               (collision_detected[i]||=is_slope(mountains[i=support_pos+i]))||mountains[i] = '|'
               }
            }
          )
      )

      # Add support to the beginning and to the end
      # of the bridge
      mountains[below] = 'Y'
    )
  )

  # Add tunnel entrance and exit
  curchar!=slope_up||in_tunnel=mountains[curindex]=41
  curchar!=slope_down||in_tunnel=mountains[curindex]=40
}

print mountains

```
> 3 votes

# Answer
## Scala, 462 characters

```
object B extends App{var r="""(?s)((?:.*\n)?)((?:.*?\n)?)(_.*?\n)(.*?\n)(.*)""".r
var r(a,b,c,d,e)=io.Source.stdin.mkString
var s=a+b.replaceAll("(?<=/ {0,99}) (?=.*\\\\)","_")+c.replaceAll("\\\\","(").replaceAll("/",")").replaceAll(" ","_")+d.replaceAll("\\\\( {3,99})  \\1/","Y$1||$1Y").replaceAll("\\\\( {3,99})  \\1\\n","Y$1||$1\n").replaceAll("\\\\( {0,9})/","Y$1Y")+e
for(i<-1 to 15)s=s.replaceAll("(?s)(?<=\\|.{"+s.split("\n")(0).size+"}) ","|")
print(s)}

```

Not particularly competitive, but I've learnt a lot about regular expressions today. :-)
> 2 votes

# Answer
# Erlang, 1182 characters

```
-module(b).
-export([t/0]).
t()->r([]).
r(R)->case io:get_line("")of eof->{_,Q}=lists:foldl(fun([$ |L],{$_,Q})->{$ ,[[$X|L]|Q]};([C|_]=L,{_,Q})->{C,[L|Q]}end,{$ ,[]},R),{_,P}=lists:foldl(fun s/2,{s,[]},lists:flatten(Q)),io:put_chars(lists:reverse(P));L->r([L|R])end.
s($X,{s,R})->{{r,s},[$ |R]};s($/,{{r,s},R})->{{r,r},[$/|R]};s($\\,{{r,r},R})->{{r,s},[$\\|R]};s($\n,{{r,_},R})->{u,[$\n|R]};s(_,{{r,r}=S,R})->{S,[$_|R]};s($_,{_,R})->{u,[$_|R]};s($\n,{u,R})->{{g,i,1,1,[]},[$\n|R]};s($\\,{u=S,R})->{S,[$(|R]};s($/,{u=S,R})->{S,[$)|R]};s(_,{u=S,R})->{S,[$_|R]};s($\\,{{g,i,X,_L,T},R})->{{g,o,X+1,X,[$Y|T]},R};s($/,{{g,o,X,L,T},R})->a(o,X,L),{{g,i,X+1,X,[$Y|T]},R};s($\n,{{g,S,X,L,T},R})->a(S,X,L),{{d,1},[$\n,f(T,X)|R]};s(C,{{g,S,X,L,T},R})->{{g,S,X+1,L,[C|T]},R};s($\n,{{d,_},R})->{{d,1},[$\n|R]};s($ ,{{d,X},R})->{{d,X+1},[case get(X)of y->$|;_->$ end|R]};s($/,{{d,X},R})->put(X,n),{{d,X+1},[$/|R]};s($\\,{{d,X},R})->put(X,n),{{d,X+1},[$\\|R]};s($\n=N,{S,R})->{S,[N|R]};s(X,{S,R})->{S,[X|R]}.
a(o,X,L)when X-L-1>6->Pos=round((X-L-1)/2+L),put(Pos,y),put(Pos+1,y);a(_,_,_)->v.
f(L,M)->{_,R}=lists:foldl(fun(C,{X,R})->case get(M-X)of y->{X+1,[$||R]};_->{X+1,[C|R]}end end,{1,[]},L),R.

```

Not competitive at all. To be honest, I was simply interested in producing some nice ascii art, not so much in the golfing. Note that this does not use regular expressions, instead, I wrote the state machine myself. This will also need the overquoting fix in the shell script, mentioned in the perl solution above.
> 2 votes

# Answer
# Powershell, ~~300~~ 295 287 bytes

*-8 bytes fix peeked from DCharness'es answer.*

```
param($s)filter e{$r,$e=$_-split'#';$e|%{$r=$r-replace($_-split';')};$r}
$x=$s-match'(.+
)?(_.+)(
.+)?'
$o,$c,$r,$b=$Matches[0..3]
for($s=$s|% *ce $o(("$c#/ ;/_"|e)+("$r# ;_#/;)#\\;("|e)+($b+'#\\(   +)  \1;\$1||$1#/|\\;Y'|e));$s-ne($x="$s#_ ;__#(?s)(?<=\|.{$($r|% Le*)}) ;|"|e)){$s=$x}$s

```

Ungolfed test script:

```
$f = {

param($s)
$x=$s-match'(.+
)?(_.+)(
.+)?'
$o,$c,$r,$b=$Matches[0..3]
$c=$c-replace'/ ','/_'                  # we assume that road does not start as a tunnel
$r=$r-replace' ','_'
$r=$r-replace'/',')'
$r=$r-replace'\\','('
$b=$b-replace'\\(   +)  \1','\$1||$1'   # we assume that road does not start as a bridge under a chasm
$b=$b-replace'/|\\','Y'
$s=$s.replace($o,"$c$r$b")              # string method replace (not operator) does not handle regexp
for(;$s-ne($x=$s-replace'_ ','__'-replace"(?s)(?<=\|.{$($r.Length)}) ",'|')){$s=$x}
$s

}

$pass = 0
$count = 0

@(
# Test 2
,(2,@'
    /\                  /\                  /\
   /  \                /  \                /  \
  /____\              /____\              /____\
_)______(____________)______(____________)______(_____
         Y    ||    Y        Y    ||    Y        Y
          \   ||   /          \   ||   /          \
           \  ||  /            \  ||  /            \
            \ || /              \ || /              \
             \||/                \||/                \
              \/                  \/
'@,@'
    /\                  /\                  /\
   /  \                /  \                /  \
  /    \              /    \              /    \
_/      \            /      \            /      \
         \          /        \          /        \
          \        /          \        /          \
           \      /            \      /            \
            \    /              \    /              \
             \  /                \  /                \
              \/                  \/
'@)

# Test 1
,(1,@'
____________________________________________________________
 Y             ||             YY             ||
  \            ||            /  \            ||
   \           ||           /    \           ||
    \          ||    /\    /      \          ||  /\        /
     \    /\   ||   /  \  /        \      /\ |/\/  \      /
      \  /  \  ||  /    \/          \    /  \/      \/\  /
       \/    \ || /                  \  /              \/
              \||/                    \/
               \/
'@,@'
_
 \                            /\
  \                          /  \
   \                        /    \
    \                /\    /      \              /\        /
     \    /\        /  \  /        \      /\  /\/  \      /
      \  /  \      /    \/          \    /  \/      \/\  /
       \/    \    /                  \  /              \/
              \  /                    \/
               \/
'@)

# Test 3
,(3,@'
    /\
   /  \
  /____\/\/\/\/\/\/\/\
_)____________________(
'@,@'
    /\
   /  \
  /    \/\/\/\/\/\/\/\
_/                    \
'@)

# Test 4
,(4,@'
___________________________________________________
 Y           ||           YY          ||          Y
  \          ||          /  \         |/\        /
   \         ||         /    \        /  \      /
    \    /\  ||    /\  /      \      /    \    /
     \  /  \ ||   /  \/        \    /      \  /
      \/    \||  /              \  /        \/
             \| /                \/
              \/
'@,@'
_
 \                        /\                      /
  \                      /  \          /\        /
   \                    /    \        /  \      /
    \    /\        /\  /      \      /    \    /
     \  /  \      /  \/        \    /      \  /
      \/    \    /              \  /        \/
             \  /                \/
              \/
'@)

# Test 5
,(5,@'
                                                      /
                                                     /
                                                    /__
___________________________________________________)___
 Y           ||           YY          ||          Y
  \          ||          /  \         |/\        /
   \         ||         /    \        /  \      /
    \    /\  ||    /\  /      \      /    \    /
     \  /  \ ||   /  \/        \    /      \  /
      \/    \||  /              \  /        \/
             \| /                \/
              \/
'@,@'
                                                      /
                                                     /
                                                    /
_                                                  /
 \                        /\                      /
  \                      /  \          /\        /
   \                    /    \        /  \      /
    \    /\        /\  /      \      /    \    /
     \  /  \      /  \/        \    /      \  /
      \/    \    /              \  /        \/
             \  /                \/
              \/
'@)

# Test 6
,(6,@'
_______________________________)
 YYYYYYYYYYYYYYYYYYYYYYYYYYYYYY
'@,@'
_                              /
 \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
'@)

# Test 7
,(7,@'
_________________________________)
 Y              ||              Y
  \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
'@,@'
_                                /
 \                              /
  \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
'@)

# Test 8
,(8,@'
      /\    /\    /\    /\    /\    /\
_)(__)__(__)__(__)__(__)__(__)__(__)__(
   YY    YY    YY    YY    YY    YY
'@,@'
      /\    /\    /\    /\    /\    /\
_/\  /  \  /  \  /  \  /  \  /  \  /  \
   \/    \/    \/    \/    \/    \/
'@)

# Test 9
,(9,@'
  /\/\/\/\/\/\/\/\
_)________________(
'@,@'
  /\/\/\/\/\/\/\/\
_/                \
'@)

# Test 10
,(10,@'
      /\                                                            /\
     /  \                                                          /  \
    /    \                                                        /    \
   /      \                                                      /      \
  /________\                                                    /________\/\/\/\/\
_)__________(__________________________________________________)__________________(______)(_________
             Y                       ||                       Y                    Y    Y  Y   ||
              \                      ||    /\                /                      \  /    \  ||  /
               \    /\               ||   /  \              /                        \/      \ || /
                \  /  \              ||  /    \            /                                  \||/
                 \/    \             || /      \          /                                    \/
                        \        /\  ||/        \        /
                         \      /  \ |/          \      /
                          \    /    \/            \    /
                           \/\/                    \/\/
'@,@'
      /\                                                            /\
     /  \                                                          /  \
    /    \                                                        /    \
   /      \                                                      /      \
  /        \                                                    /        \/\/\/\/\
_/          \                                                  /                  \      /\
             \                                                /                    \    /  \
              \                            /\                /                      \  /    \      /
               \    /\                    /  \              /                        \/      \    /
                \  /  \                  /    \            /                                  \  /
                 \/    \                /      \          /                                    \/
                        \        /\    /        \        /
                         \      /  \  /          \      /
                          \    /    \/            \    /
                           \/\/                    \/\/
'@)

# Test 11
,(11,@'
__________________________________________________
 Y     ||     YY     ||     YY         ||
  \    ||    /  \    ||    /  \        /\
   \   ||   /    \   ||   /    \      /  \    /\
    \  ||  /      \  ||  /      \    /    \  /  \/
     \ || /        \ || /        \  /      \/
      \||/          \||/          \/
       \/            \/
'@,@'
_
 \            /\            /\
  \          /  \          /  \        /\
   \        /    \        /    \      /  \    /\
    \      /      \      /      \    /    \  /  \/
     \    /        \    /        \  /      \/
      \  /          \  /          \/
       \/            \/
'@)

# Test 12
,(12,@'
                                           /\  /\
                                          /  \/  \                    /
           /\                            /        \  /\              /
    /\    /  \                          /          \/  \            /
   /  \  /    \/\                      /                \    /\    /
  /____\/________\                    /__________________\  /__\  /____
_)________________(__________________)____________________()____()_____
                   Y       ||       Y
                    \      ||    /\/
                     \  /\ ||   /
                      \/  \||  /
                           \| /
                            \/
'@,@'
                                           /\  /\
                                          /  \/  \                    /
           /\                            /        \  /\              /
    /\    /  \                          /          \/  \            /
   /  \  /    \/\                      /                \    /\    /
  /    \/        \                    /                  \  /  \  /
_/                \                  /                    \/    \/
                   \                /
                    \            /\/
                     \  /\      /
                      \/  \    /
                           \  /
                            \/
'@)

# Test 13
,(13,@'
_____________)(____________)(_____________________
 Y    ||    Y  Y    ||    Y  Y   ||   YY    ||
  \   ||   /    \   ||   /    \  ||  /  \   |/\  /
   \  ||  /      \  ||  /      \ || /    \  /  \/
    \ || /        \ || /        \||/      \/
     \||/          \||/          \/
      \/            \/
'@,@'
_            /\            /\
 \          /  \          /  \        /\
  \        /    \        /    \      /  \    /\  /
   \      /      \      /      \    /    \  /  \/
    \    /        \    /        \  /      \/
     \  /          \  /          \/
      \/            \/
'@)

# Test 14
,(14,@'
            /\            /\
___________)__(__________)__(________)(_________
 Y   ||   Y    Y   ||   Y    Y      Y  Y    YY
  \  ||  /      \  ||  /      \    /    \  /  \/
   \ || /        \ || /        \  /      \/
    \||/          \||/          \/
     \/            \/
'@,@'
            /\            /\
_          /  \          /  \        /\
 \        /    \        /    \      /  \    /\
  \      /      \      /      \    /    \  /  \/
   \    /        \    /        \  /      \/
    \  /          \  /          \/
     \/            \/
'@)

# Test 15
,(15,@'
           /\            /\
          /__\          /__\        /\
_________)____(________)____(______)__(____)(__
 Y      Y      Y      Y      Y    Y    Y  Y  YY
  \    /        \    /        \  /      \/
   \  /          \  /          \/
    \/            \/
'@,@'
           /\            /\
          /  \          /  \        /\
_        /    \        /    \      /  \    /\
 \      /      \      /      \    /    \  /  \/
  \    /        \    /        \  /      \/
   \  /          \  /          \/
    \/            \/
'@)

# Test 16
,(16,@'
          /\            /\
         /  \          /  \        /\
        /____\        /____\      /__\    /\
_______)______(______)______(____)____(__)__()
 Y    Y        Y    Y        Y  Y      YY
  \  /          \  /          \/
   \/            \/
'@,@'
          /\            /\
         /  \          /  \        /\
        /    \        /    \      /  \    /\
_      /      \      /      \    /    \  /  \/
 \    /        \    /        \  /      \/
  \  /          \  /          \/
   \/            \/
'@)

# Test 17
,(17,@'
         /\            /\
        /  \          /  \        /\
       /    \        /    \      /  \    /\
      /______\      /______\    /____\  /__\/
_____)________(____)________(__)______()_____
 Y  Y          Y  Y          YY
  \/            \/
'@,@'
         /\            /\
        /  \          /  \        /\
       /    \        /    \      /  \    /\
      /      \      /      \    /    \  /  \/
_    /        \    /        \  /      \/
 \  /          \  /          \/
  \/            \/
'@)

# Test 18
,(18,@'
        /\            /\
       /  \          /  \        /\
      /    \        /    \      /  \    /\
     /      \      /      \    /    \  /  \/
    /________\    /________\  /______\/_____
___)__________(__)__________()______________
 YY            YY
'@,@'
        /\            /\
       /  \          /  \        /\
      /    \        /    \      /  \    /\
     /      \      /      \    /    \  /  \/
    /        \    /        \  /      \/
_  /          \  /          \/
 \/            \/
'@)

# Test 19
,(19,@'
       /\            /\
      /  \          /  \        /\
     /    \        /    \      /  \    /\
    /      \      /      \    /    \  /  \/
   /        \    /        \  /      \/
  /__________\  /__________\/______________
_)____________()___________________________
'@,@'
       /\            /\
      /  \          /  \        /\
     /    \        /    \      /  \    /\
    /      \      /      \    /    \  /  \/
   /        \    /        \  /      \/
  /          \  /          \/
_/            \/
'@)

# Test 20
,(20,@'
__________________________________________________
 Y     ||     YY     ||     YY         ||
  \    ||    /  \    ||    /  \        /\
   \   ||   /    \   ||   /    \      /  \    /\
    \  ||  /      \  ||  /      \    /    \  /  \
     \ || /        \ || /        \  /      \/    \
      \||/          \||/          \/
       \/            \/
'@,@'
_
 \            /\            /\
  \          /  \          /  \        /\
   \        /    \        /    \      /  \    /\
    \      /      \      /      \    /    \  /  \
     \    /        \    /        \  /      \/    \
      \  /          \  /          \/
       \/            \/
'@)

# Test 21
,(21,@'
      /\            /\
     /  \          /  \        /\
    /    \        /    \      /  \    /\
   /      \      /      \    /    \  /  \/
  /________\    /________\  /______\/_____
_)__________(__)__________()______________
             YY
'@,@'
      /\            /\
     /  \          /  \        /\
    /    \        /    \      /  \    /\
   /      \      /      \    /    \  /  \/
  /        \    /        \  /      \/
_/          \  /          \/
             \/
'@)

# Test 22
,(22,@'
     /\            /\
    /  \          /  \        /\
   /    \        /    \      /  \    /\
  /______\      /______\    /____\  /__\/
_)________(____)________(__)______()_____
           Y  Y          YY
            \/
'@,@'
     /\            /\
    /  \          /  \        /\
   /    \        /    \      /  \    /\
  /      \      /      \    /    \  /  \/
_/        \    /        \  /      \/
           \  /          \/
            \/
'@)

# Test 23
,(23,@'
                         /\
                        /  \
                   /\  /    \
            /\    /  \/      \
           /  \  /            \                  /\
          /____\/______________\                /__\
_________)______________________(________)(____)____(_______
 Y      Y                        Y      Y  Y  Y      Y  YY
  \    /                          \    /    \/        \/  \/
   \  /                            \  /
    \/                              \/
'@,@'
                         /\
                        /  \
                   /\  /    \
            /\    /  \/      \
           /  \  /            \                  /\
          /    \/              \                /  \
_        /                      \        /\    /    \
 \      /                        \      /  \  /      \  /\
  \    /                          \    /    \/        \/  \/
   \  /                            \  /
    \/                              \/
'@)

# Test 24
,(24,@'
    /\            /\
   /  \          /  \        /\
  /____\        /____\      /__\    /\
_)______(______)______(____)____(__)__()
         Y    Y        Y  Y      YY
          \  /          \/
           \/
'@,@'
    /\            /\
   /  \          /  \        /\
  /    \        /    \      /  \    /\
_/      \      /      \    /    \  /  \/
         \    /        \  /      \/
          \  /          \/
           \/
'@)

# Test 25
,(25,@'
   /\            /\
  /__\          /__\        /\
_)____(________)____(______)__(____)(__
       Y      Y      Y    Y    Y  Y  YY
        \    /        \  /      \/
         \  /          \/
          \/
'@,@'
   /\            /\
  /  \          /  \        /\
_/    \        /    \      /  \    /\
       \      /      \    /    \  /  \/
        \    /        \  /      \/
         \  /          \/
          \/
'@)

# Test 26
,(26,@'
  /\            /\
_)__(__________)__(________)(_________
     Y   ||   Y    Y      Y  Y    YY
      \  ||  /      \    /    \  /  \/
       \ || /        \  /      \/
        \||/          \/
         \/
'@,@'
  /\            /\
_/  \          /  \        /\
     \        /    \      /  \    /\
      \      /      \    /    \  /  \/
       \    /        \  /      \/
        \  /          \/
         \/
'@)

# Test 27
,(27,@'
_)(____________)(_____________________
   Y    ||    Y  Y   ||   YY    ||
    \   ||   /    \  ||  /  \   |/\  /
     \  ||  /      \ || /    \  /  \/
      \ || /        \||/      \/
       \||/          \/
        \/
'@,@'
_/\            /\
   \          /  \        /\
    \        /    \      /  \    /\  /
     \      /      \    /    \  /  \/
      \    /        \  /      \/
       \  /          \/
        \/
'@)

# Test 28
,(28,@'
____________________________________
 Y     ||     YY         ||
  \    ||    /  \        /\
   \   ||   /    \      /  \    /\
    \  ||  /      \    /    \  /  \/
     \ || /        \  /      \/
      \||/          \/
       \/
'@,@'
_
 \            /\
  \          /  \        /\
   \        /    \      /  \    /\
    \      /      \    /    \  /  \/
     \    /        \  /      \/
      \  /          \/
       \/
'@)

# Test 29
,(29,@'
_____________________________
 Y            ||            Y
  \        /\ || /\      /\/
   \  /\  /  \||/  \  /\/
    \/  \/    \/    \/
'@,@'
_
 \                          /
  \        /\    /\      /\/
   \  /\  /  \  /  \  /\/
    \/  \/    \/    \/
'@)

# Test 30
,(30,@'
_____
 Y  Y
  \/
'@,@'
_
 \  /
  \/
'@)

# Test 31
,(31,@'
       /\
    /\/__\
___)______(__
 YY        YY
'@,@'
       /\
    /\/  \
_  /      \
 \/        \/
'@)

# Test 32
,(32,@'
      /\
     /  \
    /____\
___)______(__
 YY        YY
'@,@'
      /\
     /  \
    /    \
_  /      \
 \/        \/
'@)

# Test 33
,(33,@'
_______
 Y    Y
  \/\/
'@,@'
_
 \    /
  \/\/
'@)

# Test 34
,(34,@'
_)()()()()()()()()()()()()()()()()()(
'@,@'
_/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
'@)

) | % {
    $num, $expected, $s = $_
    $result = &$f $s
    $passed=$result-eq$expected
    "$num : $passed"
    # $result           # uncomment this line to display results

    $pass+=$passed
    $count+=1
}

"$pass/$count passed."

```

Output:

```
2 : True
1 : True
3 : True
4 : True
5 : True
6 : True
7 : True
8 : True
9 : True
10 : True
11 : True
12 : True
13 : True
14 : True
15 : True
16 : True
17 : True
18 : True
19 : True
20 : True
21 : True
22 : True
23 : True
24 : True
25 : True
26 : True
27 : True
28 : True
29 : True
30 : True
31 : True
32 : True
33 : True
34 : True
34/34 passed.

```

Explanation comics:

```
Start here:
    /\                  /\                  /\
   /  \                /  \                /  \
  /    \              /    \              /    \
_/      \            /      \            /      \
         \          /        \          /        \
          \        /          \        /          \
           \      /            \      /            \
            \    /              \    /              \
             \  /                \  /                \
              \/                  \/

Match and zoom it!
  /    \              /    \              /    \      $ceiling \
_/      \            /      \            /      \     $road    |  $outline
         \          /        \          /        \    $bottom  /

Start ceiling:
  /_   \              /_   \              /_   \      $ceiling \
_/      \            /      \            /      \     $road    |  $outline
         \          /        \          /        \    $bottom  /

Dig tunnels, build a road:
  /_   \              /_   \              /_   \      $ceiling \
_)______(____________)______(____________)______(_____$road    |  $outline
         \          /        \          /        \    $bottom  /

Attach to the road the top parts of pillars:
  /_   \              /_   \              /_   \      $ceiling \
_)______(____________)______(____________)______(_____$road    |  $outline
         \    ||    /        \    ||    /        \    $bottom  /

The road need support:
  /____\              /____\              /____\      $ceiling \
_)______(____________)______(____________)______(_____$road    |  $outline
         Y    ||    Y        Y    ||    Y        Y    $bottom  /

Put the road back into mountainous lands:
    /\                  /\                  /\
   /  \                /  \                /  \
  /_   \              /_   \              /_   \      $ceiling \
_)______(____________)______(____________)______(_____$road    |  $outline
         Y    ||    Y        Y    ||    Y        Y    $bottom  /
          \        /          \        /          \
           \      /            \      /            \
            \    /              \    /              \
             \  /                \  /                \
              \/                  \/

Build ceilings and build down pillars:
    /\                  /\                  /\
   /  \                /  \                /  \
  /__  \              /__  \              /__  \
_)______(____________)______(____________)______(_____
         Y    ||    Y        Y    ||    Y        Y
          \   ||   /          \   ||   /          \
           \      /            \      /            \
            \    /              \    /              \
             \  /                \  /                \
              \/                  \/

A few iterations later...
    /\                  /\                  /\
   /  \                /  \                /  \
  /____\              /____\              /____\
_)______(____________)______(____________)______(_____
         Y    ||    Y        Y    ||    Y        Y
          \   ||   /          \   ||   /          \
           \  ||  /            \  ||  /            \
            \ || /              \ || /              \
             \||/                \||/                \
              \/                  \/

Thanks. But our princess is in another castle!

```
> 1 votes

---
Tags: code-golf, ascii-art
---


title: Special quines and code golf, hooray!

text:
# Question
Title: Special quines and code golf, hooray!
Make a quine. Simple enough, except it has to be a palindrome and accept input.

Now, any side of a palindromic quine is one half of it. For example, one side of the hypothetical quine AAAA is AA. One side of AAAAA is AA (the center symbol is ignored).

Your job is to make a quine like this that accepts input. If the input is the whole quine, then the quine prints the left side of itself. If the input is either side of the quine then the quine prints itself. Of course, with quines with an odd number of symbols the center symbol is ignored. If the input is anything other than the cases specified, the program must do nothing.

This is code golf, so the shortest submission wins.

# Answer
# Javascript, ~~224~~ 200 bytes

Prompts for input. I shaved off some bytes by using ES6 features. Still can probably be golfed a lot more.

```
(f=_=>{a=prompt();s=`(f=${f})()/`;r=[...s].reverse().join('');return a==s||a==r?s+r:a==s+r?s:""})()//)()}"":s?r+s==a:r+s?r==a||s==a nruter;)''(nioj.)(esrever.]s...[=r;`/)()}f{$=f(`=s;)(tpmorp=a{>=_=f(
```
> 2 votes

# Answer
# Haskell, ~~350~~ ~~346~~ 342 bytes

```
main=interact f;f s|s==l++r=l|s/=l,s/=r=[]|1<3=l++r;r=reverse l;l=q++shows q['-'];q="main=interact f;f s|s==l++r=l|s/=l,s/=r=[]|1<3=l++r;r=reverse l;l=q++shows q['-'];q="--"=q;]'-'[q swohs++q=l;l esrever=r;r++l=3<1|][=r=/s,l=/s|l=r++l==s|s f;f tcaretni=niam"=q;]'-'[q swohs++q=l;l esrever=r;r++l=3<1|][=r=/s,l=/s|l=r++l==s|s f;f tcaretni=niam

```

*Edit: -8 bytes thanks to Ørjan Johansen! Also changed to a version which does not need `(<>)`.*
> 3 votes

---
Tags: code-golf, quine
---


title: Integer Linear Programming

text:
# Question
Title: Integer Linear Programming
# Introduction

Write a solver for integer linear programming.

# Challenge

Your task is write a solver for integer linear programming (ILP). In ILP, linear inequalities of a set of unknowns (all of which are integers) are given, and the goal is to find the minimum or maximum of a linear function.

For example, for the inequalities (example taken from Mixed Integer Linear Programming)

```
 4x+2y-15≤0
  x+2y- 8≤0
  x+ y- 5≤0
- x      ≤0
   - y   ≤0

```

and the objective function `3x+2y`, the maximum of the objective function should be `12` (`x=2,y=3`), while the minimum should be `0` (`x=y=0`).

The input is given as an 2d array (or any equivalent following the standard specifications), each row corresponds to one inequality, with the exception of the final row. The numbers in the array are the coefficients, and the `≤0` part is always omitted. If there are `n` elements in each row, it means there are `n-1` unknowns.

The last row of the array correspond to the linear function. The coefficients are listed.

For example, the input array for the problem above is

```
[[4,2,-15],[1,2,-8],[1,1,-5],[-1,0,0],[0,-1,0],[3,2,0]].

```

The output should be the minimum and the maximum, given in any reasonable form.

For the following problem (two of the restrictions are taken away from the problem above):

```
[[4,2,-15],[1,2,-8],[1,1,-5],[3,2,0]].

```

The maximum is still `12`, but the minimum does not exist and the objective function can have arbitrarily large (in the sense of absolute value) negative values. In this case, the program should output `12`, following a falsy value that is decided by the answerer. Another case is that there are no solution at all, for example,

```
[[4,2,-15],[-1,-2,7],[-1,0,3],[0,1,0],[3,2,0]].

```

In this case, falsy values should be output as well. It would be nice to discern the case where the "optimal value" for the objective function is infinity and the case where there are no solutions at all, but this is not necessary.

The input only contains integer coefficients both for the inequalities and for the objective function. **All** the unknowns are also integers. The coefficient matrix of the inequalities is guaranteed to have full rank.

# Test Cases

Credit to @KirillL. for finding a bug in the original test suite and deepening my understanding of ILP problems.

```
Input
Output

[[4,2,-15],[1,2,-8],[1,1,-5],[-1,0,0],[0,-1,0],[3,2,1]]
[1,13]

[[4,2,-15],[1,2,-8],[1,1,-5],[3,2,0]]
[-inf, 12]

[[4,2,-15],[-1,-2,7],[-1,0,3],[0,1,0],[3,2,0]]
[NaN, NaN]

[[-1,-1,-1,-1,-1,8],[1,1,1,1,0,0],[5,5,5,5,6,7]]
[55, inf]

[[-1,-1,-1,-1,-1,8],[1,1,1,1,0,0],[0,0,0,0,0,4]]
[4, 4]

[[4,2,-15],[-1,-2,7],[-1,0,3],[0,1,0],[0,0,4]]
[NaN, NaN]

```

# Specs

* No need to worry about exception handling.
* This is , the lowest number of bytes wins.
* Maximal number of unknowns: `9`. Maximal number of inequalities: `12`.
* You can take input and provide output through any standard form, and you are free to choose the format.
* As usual, default loopholes apply here.

# Answer
> 2 votes
# Python 3, 534 bytes

```
import itertools as t
import operator as o
I=float("inf")
e=lambda p,A:sum([i[0]*i[1]for i in zip(p,A[:-1])])+A[-1]
def w(x,j):
	d=len(x[0])-1;C=[0]*d;v,w=I,I
	while 1:
		L={(*n,):(sum([0 if e(n,A)<=0 else e(n,A)for A in x[:-1]]),j*e(n,x[-1]))for n in [[sum(a) for a in zip(C,c)]for c in t.product(*[[-1,0,1]]*d)]};C,P=min(L.items(),key=o.itemgetter(1))[0],C;v,w,p,q=L[C][0],L[C][1],v,w
		if(all([e(C,A)<=e(P,A)for A in x[:-1]]))*(j*(e(C,x[-1])-e(P,x[-1]))<0)+(p==v>0):return I
		if(p==v)*(q<=w):return j*q
f=lambda x:(w(x,1),w(x,-1))

```

Try it online!

## Overview

It is an iterative algorithm, starting from the origo. It collects the neighbour positions and assigns a potential function: `x:(a,b)` where `x` is the position, `a` is the sum of the position's distances from the half-spaces of each linear inequality, `b` is the value of the objective at that position.

`x:(a,b) < y:(c,d)` iff `a<c` or `a=c and b<d`

The iteration stops, when:

* the first coordinate of the potential hasn't decreased and positive: the system is infeasible
* the distance from every half-space has decreased just like the objective: the system is unbounded.
* none of previous and the potential hasn't decreased: it is the optimal value.

# Answer
> 1 votes
## Matlab, 226 bytes

**DISCLAIMER**: *Not an "original" implementation, only for fun.*

Simple solution taking advantage of the `intlinprog` function:

```
function r=f(a);b=-1*a(1:end-1,end);p=a(end,1:end-1);c=a(1:end-1,1:end-1);[~,f,h]=intlinprog(p,1:size(a,2)-1,c,b);[~,g,i]=intlinprog(-p,1:size(a,2)-1,c,b);s=[inf,nan,f];t=[inf,nan,g];r=a(end,end)+[s(4-abs(h)) -t(4-abs(i))];end

```

It returns the optimal values, or inf (-inf) if the problem is unbounded or nan if it is infeasible.

```
a = [4 2 -15; 1 2 -8; 1 1 -5; -1 0 0; 0 -1 0; 3 2 1]
b = [4 2 -15; 1 2 -8; 1 1 -5; 3 2 0]
c = [4 2 -15; -1 -2 7; -1 0 3; 0 1 0; 3 2 0]
d = [-1 -1 -1 -1 -1 8;  1 1 1 1 0 0; 0 0 0 0 0 4]
e = [4 2 -15; -1 -2 7; -1 0 3; 0 1 0; 0 0 4]

>> f(a)
ans =

     1    13

>> f(b)
ans =

   Inf    12

>> f(c)
ans =

   NaN   NaN

>> f(d)
ans =

     4     4

>> f(e)
ans =

   NaN   NaN

```

---
Tags: code-golf, math, optimization
---


title: Nth subset of a set

text:
# Question
Title: Nth subset of a set
## The task

Given the set

$$S = \left\[{1,2,3,4,5,6,7,8}\right\]$$

and an integer

$$0 \leq N \< 2^{|S|}$$

find the Nth subset.

## Input/Output

*N* is given as an unsigned integer on stdin. You must print the Nth subset in a format suitable for your language (this may include `[1,2,3]`,`{1,2,3}`,`[1, 2, 3]`,`1 2 3`,`1,2,3` etc. for as long as it is a human readable *text* format).

## A little bit about subsets

There is a relationship between subsets and numbers in base two. Each digit $$d\_{i}$$ specifies whether the *i*th element of the set is within the subset. For example *00000000* would be the empty set and *10000001* is the subset containing `[1,8]` (the last and first element). You get the Nth subset by converting the number into base 2 and then the subset includes all elements where $$d\_{i} \> 0$$. The 3rd subset (3 = 00000011) thus contains `[1,2]`. The rightmost digit is digit #0. It's ok to print `[2,1]`. The set does not have to be sorted.

**Addendums:**

Yes, the set is fixed to `1..8`. The set is not part of the input. Input is just *N*.

Yes, you may use alternate input forms.

All expected outputs for all *N*: https://tio.run/##SyotykktLixN/f/fyNS02qIoP8soJd1CwSAg2kY32LPWPaoqs7jg/38A

# Answer
# Jelly, 3 bytes

```
BUT

```

Try it online!

### How it works

```
BUT  Main link. Argument: n

B    Binary; convert n to base 2.
 U   Upend; reverse the resulting array, so it starts with the LSB.
  T  Truth; find all 1-based indices of set bits.

```
> 17 votes

# Answer
# , ~~52~~ 26 bytes

```
which(intToBits(scan())>0)

```

Try it online!

Converts the input to its bits and returns the 1-based indices of where they are `TRUE`. That makes this a port of Dennis' Jelly answer.

Returns `integer(0)`, the empty list of integers, for input of `0`.
> 7 votes

# Answer
# Python 2, 40 bytes

```
lambda x:[i+1for i in range(8)if x>>i&1]

```

Try it online!
> 5 votes

# Answer
# Perl 6, 33 bytes

```
(1..*Zxx*.base(2).flip.comb).flat

```

Try it online!
> 4 votes

# Answer
# Python 2, 42 bytes

```
f=lambda n,k=1:n*[k]and n%2*[k]+f(n/2,k+1)

```

Try it online!
> 3 votes

# Answer
# Japt, 7 bytes

```
ì2 Ôi ð

```

Try it

```
ì2          :Convert to base-2 digit array
   Ô        :Reverse
    i       :Prepend null element
      ð     :0-based indices of truthy elements

```

---

```
¤¬²Ôð¥1

```

Try it

```
¤           :Convert to base-2 string
 ¬          :Split
  ²         :Push 2
   Ô        :Reverse
    ð       :0-based indices of elements
     ¥1     :  Equal to 1

```
> 2 votes

# Answer
# Haskell, ~~55~~ 54 bytes

```
s n=[x|(x,d)<-zip[8,7..]$mapM(pure[0,1])[1..8]!!n,d>0]

```

Outputs the set in reversed order, try it online!

### General version, 56 bytes

This will work for sets larger than \\$\\{i\\}\_{i=1}^8\\$:

```
s n=[x|(x,d)<-zip[n,n-1..]$mapM(pure[0,1])[1..n]!!n,d>0]

```

Try it online!

## Explanation

The term `mapM (pure [0,1]) [1..n]` generates the list (`n=4`) `[[0,0,0,0],[0,0,0,1],[0,0,1,0],..,[1,1,1,1]]` \- ie. the binary representations of `[0..2^n-1]`. Indexing into it with `n` gives us the binary representation of `n`.

Now we can just `zip` it with the reversed numbers `[1..n]` and only keep the elements where the binary-digit is non-zero:

```
 [ x | (x,digit) <- zip [n,n-1,..1] binaryRepN, digit > 0 ]

```
> 2 votes

# Answer
# K4, 7 bytes

**Solution:**

```
1+&|2\:

```

**Example:**

First 10...

```
q)k)(1+&|2\:)@'!10
`long$()
,1
,2
1 2
,3
1 3
2 3
1 2 3
,4
1 4

```

**Explanation:**

```
1+&|2\: / the solution
    2\: / convert to base-2
   |    / reverse
  &     / indices where true
1+      / add 1

```
> 2 votes

# Answer
## MATLAB/Octave, ~~31~~ ~~29~~ 27 bytes

```
@(n)9-find(dec2bin(n,8)-48)

```

Try it online!
> 2 votes

# Answer
# Husk, 5 bytes

```
`fN↔ḋ

```

Takes input as command-line argument not on *stdin* (I hope this is ok), try it online!

## Explanation

```
`fN↔ḋ  -- example input: 6
    ḋ  -- convert to binary: [1,1,0]
   ↔   -- reverse: [0,1,1]
`      -- flip the arguments of
 fN    -- | filter the natural numbers by another list
       -- : [2,3]

```
> 1 votes

# Answer
# Charcoal, 11 bytes

```
↓⭆⮌↨Ｎ²×ιＩ⊕κ

```

Try it online! Link is to verbose version of code. If printing the answer horizontally without spaces is acceptable then the first character can be removed. Explanation:

```
    Ｎ       Input as a number
   ↨        Converted to base
     ²      Literal 2
  ⮌         Reversed
 ⭆          Map over bits and join
          κ Current index (0-indexed)
         ⊕  Incremented
        Ｉ   Cast to string
       ι    Current bit
      ×     Repeat string
↓           Print vertically

```
> 1 votes

# Answer
# JavaScript (ES6), 37 bytes

+4 bytes if a separator is mandatory
+3 bytes if this separator is a comma and a leading comma is allowed

```
f=(n,i=1)=>n?(n&1?i:'')+f(n/2,i+1):''

```

Try it online!
> 1 votes

# Answer
# , 13 10 bytes

```
-3 bytes thanks to Bubbler

1+I.@|.@#:

```

Try it online!
> 1 votes

# Answer
# Perl 6, 21 bytes

```
{1 X+grep $_+>*%2,^8}

```

Try it online!

Alternative:

```
{grep $_*2+>*%2,1..8}

```
> 1 votes

# Answer
# Common Lisp, 57 bytes

```
(lambda(x)(dotimes(i 7)(format(logbitp i x)"~a "(1+ i))))

```

Try it online!
> 1 votes

# Answer
# Haskell, 33 bytes

```
s n=[x+1|x<-[0..7],odd$div n$2^x]

```

Try it online!

---

**37 bytes**

```
concat.(mapM(\i->[[],[i]])[8,7..1]!!)

```

Try it online!

Test cases from nimi.
> 1 votes

# Answer
# C# (Visual C# Interactive Compiler), 47 bytes

```
x=>{for(int y=0;y<8;)if((1&x>>y++)>0)Print(y);}

```

Try it online!

Looks similar to the Java solution now, although I came up with mine independently.
> 1 votes

# Answer
# Japt, 7 bytes

```
¢Ô¬ðÍmÄ

```

Test it online

---

# Japt, 7 bytes

```
¤Ôð1 mÄ

```

Test it online
> 1 votes

# Answer
## Python 3.6, 58 bytes

```
f=lambda n:[8-v for v,i in enumerate(f'{n:08b}')if int(i)]

```
> 0 votes

# Answer
# Wolfram Language (Mathematica), 32 bytes

```
Pick[r=Range@8,BitGet[#,r-1],1]&

```

Try it online!
> 0 votes

# Answer
# Pari/GP, 31 bytes

```
n->[x|x<-[1..8],bittest(n,x-1)]

```

Try it online!
> 0 votes

# Answer
# APL+WIN, 13 bytes

Prompts for N:

```
((8⍴2)⊤⎕)/⌽⍳8

```

Try it online! Courtesy of Dyalog Classic

Explanation:

```
((8⍴2)⊤⎕) prompt for N and convert to binary

/⌽⍳8 generate a vector from 1 to 8, reverse and select integers according to 1s in binary

```

Returns subset in reverse order
> 0 votes

# Answer
## Burlesque - 8 bytes

```
8roR@j!!

```

Try it online.
> 0 votes

# Answer
# Oracle SQL, 77 bytes

```
select*from(select rownum r,value(p)from t,table(powermultiset(x))p)where:n=r

```

Test in SQL Plus

```
SQL> var n number
SQL> exec :n:=67;

PL/SQL procedure successfully completed.

SQL> with t as (select ku$_vcnt(1,2,3,4,5,6,7,8) x from dual)
  2  select*from(select rownum r,value(p)from t,table(powermultiset(x))p)where:n=r
  3  /
        67
KU$_VCNT('1', '2', '7')

```
> 0 votes

# Answer
# MathGolf, 8 bytes

```
â^mÉ┤\*─

```

Try it online!

## Explanation

```
â         Convert first input to binary list
 ^        Zip with [1,2,3,4,5,6,7,8] (other input)
  mÉ      Map 2D array using the next 3 instuctions
    ┤     Pop from right of array
     \*   Swap top two elements and repeat array either 0 or 1 times
       ─  Flatten to 1D array

```

## Alternate output format

With a more flexible output format (that I personally think looks quite good) I can come up with a 6-byter:

```
â^É┤\*

```

Instead of mapping, I use the implicit for-each, and I skip the flattening. Output looks like this:

```
[1][2][][4][5][6][7][]

```
> 0 votes

# Answer
# Ruby, 31 bytes

```
->n{n.times{|a|n[a]>0&&p(-~a)}}

```

Try it online!
> 0 votes

# Answer
# F# (Mono), 45 bytes

```
let m x=Seq.where(fun y->x>>>y-1&&&1>0)[1..8]

```

Try it online!

I also implemented a generic/recursive function, but its pretty ugly and the byte count is a ***lot*** larger...

# F# (Mono), 107 bytes

```
let rec g y i=
 if y>0 then seq{
  if y%2>0 then yield i
  yield!g(y/2)(i+1)
 }else Seq.empty
let f x=g x 1

```

Try it online!
> 0 votes

# Answer
# 05AB1E, 6 bytes

```
bRSƶ0K

```

Try it online or verify all possible test cases.

**Explanation:**

```
b         # Convert the (implicit) integer input to binary
          #  i.e. 22 → "10110"
 R        # Reverse it
          #  i.e. "10110" → "01101"
  S       # Convert it to a list of 0s and 1s
          #  i.e. "01101" → ["0","1","1","0","1"]
   ƶ      # Multiply each with its 1-indexed index
          #  i.e. ["0","1","1","0","1"] → [0,2,3,0,5]
    0K    # Remove all 0s (and output implicitly)
          #  i.e. [0,2,3,0,5] → [2,3,5]

```
> 0 votes

# Answer
# Java 8, 58 bytes

```
n->{for(int i=0;i<8;)if((1&n>>i++)>0)System.out.print(i);}

```

Try it online.

**Explanation:**

```
n->{                        // Method with integer as parameter and no return-type
  for(int i=0;i<8;)         //  Loop `i` in the range [0,8):
    if((1&n>>i++)>0)        //   If 1 AND `n` bitwise right-shifted to `i` is larger than 0
                            //   (with `i` increased by 1 afterwards with `i++`)
      System.out.print(i);} //    Print `i+1`

```
> 0 votes

---
Tags: code-golf
---


title: Multiplication by Self-Modification

text:
# Question
Title: Multiplication by Self-Modification
...at least for some definition of "self-modification".

# The Task

In this challenge, your task is to write three strings `A`, `B` and `C` that satisfy the following properties.

* The string `B` has length at least 1.
* For every `n ≥ 0`, the string `AB<sup>n</sup>C` is a valid program (meaning full runnable program or function definition) in your programming language of choice. The superscript denotes repetition, so this means the strings `AC`, `ABC`, `ABBC`, `ABBBC` etc. Each program takes one string as input, and returns one string as output.
* For any `m, n ≥ 0`, if the program `AB<sup>m</sup>C` is run with input `AB<sup>n</sup>C`, it returns `AB<sup>m*n+1</sup>C`. For inputs not of this form, the program may do anything, including crash.

Some examples in the format `program(input) -> output`:

```
AC(AC) -> ABC
ABC(AC) -> ABC
ABBBBBC(AC) -> ABC
AC(ABC) -> ABC
AC(ABBBBC) -> ABC
ABC(ABC) -> ABBC
ABBC(ABC) -> ABBBC
ABBBBC(ABBBC) -> ABBBBBBBBBBBBBC
ABBBC(ABBBBBBC) -> ABBBBBBBBBBBBBBBBBBBC

```

# Rules and Scoring

Your score is the **total length of `A` and `C`**, lower score being better. Note that while `B` is not counted toward the score, it must be produced by `A` and `C` as in the first example.

Standard loopholes are disallowed. The programs are not allowed to directly or indirectly access their own source code (except when they are given it as input). You are required to identify the strings `A`, `B` and `C` in your answer in some way, and encouraged to explain your solution.

# Answer
> 17 votes
# CJam, ~~9~~ 8 bytes

```
A: 1
B: 0
C:  r,(#0q

```

Try it online in the CJam interpreter.

### How it works

```
(ABcode) e# Push the integer 10 ** len(Bcode).
<SP>     e# Noop. Separates (AB) and C for input reading.
r        e# Read the first whitespace-separated token from STDIN (ABinput).
,(       e# Push the string length minus 1: len(Binput)
#        e# Power operator: 10 ** len(Bcode) len(Binput) # ->
         e#   (10 ** len(Bcode)) ** len(Binput) = 10 ** (len(Bcode) * len(Binput))
0        e# Push an additional 0 to complete len(Bcode) * len(Binput) + 1 zeroes.
q        e# Read the remaining input (C).

```

# Answer
> 12 votes
# CJam, ~~15~~ ~~13~~ 11 bytes

```
A: rl"
B: <SP>
C: <LF>",(*SNq

```

Try it online in the CJam interpreter.

### How it works

```
e# A

r     e# Read a whitespace-separated token from STDIN.
      e# This reads the input up to the first space, but does not consume it.
l     e# Read the rest of the first line from STDIN.
      e# This reads up to the first linefeed and consumes it.

"     e# Initiate a string.

e# B

<SP>  e# Fill the string with as many spaces as there are copies of B.

e# C

<LF>" e# Terminate the string with a linefeed.
      e# This serves as a delimiter for the `l' command.
,(    e# Compute the length of the string minus 1 (to account for the LF).
*     e# Repeat the string read by `l' that many times.
SN    e# Push a space and a linefeed.
q     e# Read the remaining input (i.e., the second line) from STDIN.

```

At the end, the stack contains the token read by `r`, the space produced by `*`, the space and linefeed pushed by `SN` and the line read by `q`. CJam prints all these automatically.

# Answer
> 9 votes
# Pyth, 10

```
A: w*\0hl*w[<newline>
B: 0
C: <empty>

```

We split the source in two lines. The first line is A, the second line are the Bs. Since A is on the first line, the first `w` just prints A - easy, done.

In Pyth leading zeroes are seperate tokens, so `[00)` actually is `[0, 0]`. Note that the first line ends in `l[`, and the second line consists of `0000...`. So `l[` actually counts the number of Bs in this program. The second `w` reads in the second line of the input - this is the number of Bs of the input. From here it's a simple multiply, increment and outputting that many zeroes.

# Answer
> 9 votes
# Retina, ~~25~~ 19 bytes

```
A: ]\]<LF>
B: ]]
C: <LF>m`^]*$<LF>]$0]

<LF> stands for newline

```

Example `ABC` code:

```
]\]
]]
m`^]*$
]$0]

```

The code has two substitute steps:

* change the input `AB^mC` into `AB^(m*n)C` by changing every `B` to `B^n`:

+ `]\]` matches every `B` in the input and nothing else thanks to escaping in the pattern lines
    + `]]...]]` is `B^n`
* change `B^(m*n)` to `B^(m*n+1)` by

+ `m`^]*$` taking the line with only `]`'s
    + `]$0]` adding an extra pair of `]]` to it in a way that this line doesn't match the first regex

I've added 3 bytes to the score for the `-s` multi-line flag which is needed so the whole Retina code could be in one file.

2 bytes saved thanks to @MartinBüttner.

# Answer
> 8 votes
# Python 3, 51 bytes

```
A: lambda s:s[:28]+"x"*(1+len("
B: x
C: ")*(len(s)-51))+s[-23:]

```

Example usage:

```
>>> f=lambda s:s[:28]+"x"*(1+len("xx")*(len(s)-51))+s[-23:]
>>> f('lambda s:s[:28]+"x"*(1+len("xxx")*(len(s)-51))+s[-23:]')
'lambda s:s[:28]+"x"*(1+len("xxxxxxx")*(len(s)-51))+s[-23:]'

```

The function computes `n*m+1` with `(1+len("xxx")*(len(s)-51))` where there are `m` `x`'s in the string (`xxx` part is the `B^m`). Multiplying the string `"x"` with this number gives `B^(n*m+1)` and the function takes `A` and `C` out of the input and concatenates all of these to get `AB^(n*m+1)C`.

The same approach in J:

# J, 35 bytes

```
A: (19{.]),('x'#~1+(#'
B: x
C: ')*35-~#),_16{.]

```

# Answer
> 5 votes
# CJam, 22

```
A:<empty>
B:{])`\,q,K/(*))*"_~"}
C:{])`\,q,K/(*))*"_~"}_~

```

Example run:

```
ABBC(ABC) -> ABBBC

```

which translates to

```
{])`\,q,K/(*))*"_~"}{])`\,q,K/(*))*"_~"}{])`\,q,K/(*))*"_~"}_~

```

with input as

```
{])`\,q,K/(*))*"_~"}{])`\,q,K/(*))*"_~"}_~

```

which gives the following output:

```
{])`\,q,K/(*))*"_~"}{])`\,q,K/(*))*"_~"}{])`\,q,K/(*))*"_~"}{])`\,q,K/(*))*"_~"}_~

```

**How it works**:

Lets take a look at what programs `AC` and `ABC` look like:

```
AC :{])`\,q,K/(*))*"_~"}_~
ABC:{])`\,q,K/(*))*"_~"}{])`\,q,K/(*))*"_~"}_~

```

We notice that `C` = `B_~`

Lets look at what `B` is doing:

```
{])`\,q,K/(*))*"_~"}

{                  }    e# This is a code block. Alone, this does nothing except
                        e# pushing this block to stack as is
 ]                      e# Wrap everything on stack in an array
  )`                    e# Take out the last part and convert it to its string representation
    \,                  e# Take length of remaining array
      q,K/              e# Read the input, take its length and int divide by K (i.e. 20)
          (*            e# Decrement and multiply by the array length on stack
            ))          e# Add two to the product
              *         e# Repeat the string representation on stack that many times
               "_~"     e# Put this string on stack

```

Now lets see what running `AC` without any input will do:

```
{])`\,q,K/(*))*"_~"}_~                      e# Copy the block and run it
{])`\,q,K/(*))*"_~"}{])`\,q,K/(*))*"_~"}~   e# Block is copied, run it
{      ...         } ])                     e# Wrapped array has the block in it.
                       `\,                  e# Stringify it and take length of remaining = 0
                          q,K/              e# No input so 0
                              (*))          e# 0 * -1 = 0. 0 + 2 = 2
                                  *         e# Repeat the stringified block 2 times:
                                            e# "{])`\,q,K/(*))*"_~"}{])`\,q,K/(*))*"_~"}"
                                   "_~"     e# Put this string. Program ends, so print stack:
                                            e# {])`\,q,K/(*))*"_~"}{])`\,q,K/(*))*"_~"}_~

```

Wow, the output is `ABC`.

We basically count how many `B` exist in the code. Then how many are in the input (using length). Multiply them, increment twice (since `C` also has `B`) and append `_~` to get `C`

Try it online here

# Answer
> 3 votes
# Haskell, 50 bytes

`f` is a function taking and returning a `String`.

The string B is just a single space, while C starts with one.

```
A:_:b="
B:
C: ";f s|a:c<-words s=unwords$a:(drop 50s>>b):c

```

Try it online!

* `_:b=" "` assigns all but the first of the spaces in the string literal to `b`, making that equal to the program's *m* B copies.
* `s` is the input string. `a:c<-words s` splits it into space-separated words, so that `a` becomes A and `c` becomes a list of the words comprising C. The B copies are ignored since `words` squeezes multiple spaces (which the rest of the program avoids).
* `drop 50s` is a string with length equal to the number *n* of B copies in the input. `drop 50s>>b` concatenates that many copies of `b`, giving *mn* spaces.
* `unwords$a:(drop 50s>>b):c` joins all the strings back together with spaces. Since there is an extra "word" `(drop 50s>>b)` inserted in the list, there is also an extra joining space, automatically adding the +1 to the multiplication.

# Answer
> 2 votes
# Matlab, 85

First time for me to do such an abstract challenge, so for me it was more of a coding challenge than a code-golf challenge!

The three strings are, without the quotation marks:

```
A:    "X=strsplit(input('','s'));m=0 "
B:    "+1 "
C:    ";[X{1},32,repmat(['+1',32],1,m*(length(X)-2)+1),X{end}]"

```

**How it works:** I split the input argument on whitespace, so `n` can be determined from the number of string parts. B works as a sort of counter to get `m`. For reconstructing the answer I use A and C from the split, repeat B m\*n+1 times and I insert the spaces by using their ASCII value, so that no unwanted splits occur in C.

EDIT: whoops, accidentally counted A+B

# Answer
> 1 votes
# C (gcc), 81 bytes

The requirement to identify the strings seems at odds with our being allowed arbitrary behaviour for illegal input, unless we have rather lax standards of what identifying entails. Naturally, I took the interpretation that sheds the most bytes.

Try it online!

```
A: m;f(char*s){m=strrchr(s+66,32)-s-65;printf("%.66s%*s",s,m*strlen("
B: <SPACE>
C: ")+16,s+m+66);}

```

# Answer
> 1 votes
# TI-Basic (83 series), 65 bytes

Segment A (33 bytes):

```
Input Str1:sub(Str1,1,27:For(I,0,(length(Str1)-55)(length("

```

Segment B:

```
X

```

Segment C (32 bytes):

```
Y")-1:Ans+"X":End:Ans+sub(Str1,length(Str1)-27,28

```

---

I am really excited about finding this quine-like challenge! Most quines don't work in TI-Basic without at least a little cheating, because there is no way to escape the `"` symbol. (In both senses of the word "escape".) But here, we get an input string via the `Input` command, and typing in a `"` there is perfectly fine.

There is still some amount of TI-Basic silliness to work around here: an empty string is invalid, so the naive solution of inserting the string `"XXX...XX"` in a loop won't work when n=0. Instead, we manually compute the value of mn+1, and insert the string `"X"` that many times.

The magic constants `27` and `28` in the program are slightly off from the byte counts 33 and 32, because `Str1`, `sub(`, and `length(` are two-byte tokens that only contribute 1 to the length of a string.

If we use newlines instead of `:`, it looks like when can save a few bytes by leaving off ending quotes, but this doesn't actually work. First of all, you need a hex editor before you can add the newline character into a string: you can't just type it in, because if you press ENTER during an `Input` command, it submits the input. When I tried the hex editor approach, I ended up getting a weird buffer overflow error that modified the contents of my program, so don't try this at home with your expensive calculator.

# Answer
> 0 votes
# Java 11, ~~135~~ 65+26=91 bytes

**A**

```
s->{var p=s.split("\\(\"|\"\\.");return p[0]+"(\"B"+p[1].repeat("

```

**B**

```
B

```

**C**

```
".length())+'"'+'.'+p[2];}

```

Try it online here (TIO does not have Java 11 yet, so this relies on a helper method instead of `String::repeat()`).

Ungolfed:

```
s -> { // lambda taking and returning a String
    var p = s.split("\\(\"|\"\\."); // split input into parts A, B^n, C (where n may be 0) at the "(\"" and "\"."
    return p[0] + "(\"B" + // put it back together: A plus the part the split shaved off, plus an extra B ...
    p[1].repeat("BBB".length()) + // ... plus B^(n*m)
    '"' + '.' + p[2]; // plus C, with the part the split shaved off reattached
}

```

---
Tags: code-golf, quine, source-layout
---


title: Egyptian Pyramids

text:
# Question
Title: Egyptian Pyramids
The Great Pyramid of Giza, the largest pyramid in Egypt, is not only the oldest of the Seven Wonders of the Ancient World, but it is also the **only** one to remain largely intact. The Egyptian Pyramids can take up to 20 years to build and are so big that Al-Aziz Uthman, son of the great Saladin who crushed the Crusaders, had to give up demolishing the Great pyramids of Giza because it was deemed **too great a task**. The Egyptian pyramids were mostly built as tombs for the country's Pharaohs and their consorts during the Old and Middle Kingdom periods (c. 2686–1690 BCE), and as of 2008, 138 Egyptian pyramids have been discovered.

The task is to create a program which inputs a sequence of distances separated by a space, and produces 10×10 text pyramids separated by those distances. A distance of 1 is equal to two characters.

A text pyramid will look like this:

```
         /\
        /--\
       /----\
      /------\
     /--------\
    /----------\
   /------------\
  /--------------\
 /----------------\
/------------------\

```

**If the input consists of only a line break, then one pyramid will be produced, as above**. For each pyramid, pyramids to the left are displayed as if they were in front.

## Example I

Input:

```
4 3 1

```

Output:

```
         /\      /\    /\/\
        /--\    /--\  /--\-\
       /----\  /----\/----\-\
      /------\/------\-----\-\
     /--------\-------\-----\-\
    /----------\-------\-----\-\
   /------------\-------\-----\-\
  /--------------\-------\-----\-\
 /----------------\-------\-----\-\
/------------------\-------\-----\-\

```

## Example II

Input:

```
0 9

```

Output:

```
         /\                /\
        /--\              /--\
       /----\            /----\
      /------\          /------\
     /--------\        /--------\
    /----------\      /----------\
   /------------\    /------------\
  /--------------\  /--------------\
 /----------------\/----------------\
/------------------\-----------------\

```

## Example III

Input:

```
11

```

Output:

```
         /\                    /\
        /--\                  /--\
       /----\                /----\
      /------\              /------\
     /--------\            /--------\
    /----------\          /----------\
   /------------\        /------------\
  /--------------\      /--------------\
 /----------------\    /----------------\
/------------------\  /------------------\

```

The application to fulfill these requirements in the fewest amount of characters is the winner.

Reference: Wikipedia.org

# Answer
> 4 votes
## Golfscript, 70 characters

```
~]0-:|;10,{:§9\-" "*"/""-"§2**+"\\"+:&|{.§>{§-(2*" "*1$}{-2*&>}if}%n}%

```

Direct port of my Ruby solution, so I'm sure it's possible to shorten this by quite a few characters.

# Answer
> 5 votes
## Windows PowerShell, 122 ~~132~~ ~~133~~ ~~139~~

```
$d=@(-split$input)-gt0
0..9|%{' '*(9-($x=$_))+($a="/$('--'*$_)\")+-join($d|%{'  '*(($_-$x-1)*($x-lt$_))
$a[(-2*$_)..-1]})}

```

Test script.

Random input also makes for nice images:

# Answer
> 4 votes
## Haskell, 148 characters

```
r=replicate
p d=map(\k->foldr(\n i->r(9-k)' '++'/':r(2*k)'-'++"\\"++drop(11+k)(r(2*n)' '++i))""$d++[0])[0..9]
main=interact$unlines.p.map read.words

```

I'm quite unsatisfied with this! It just feels way too long. Ideas?

# Answer
> 4 votes
## Ruby 1.9, 116 characters

```
d=gets.split-[?0]
10.times{|i|puts [?\s*(9-i),l=?/+?-*2*i+?\\,d.map{|r|i<(r=r.to_i)??\s*2*(r+~i)+l :l[-2*r,99]}]*""}

```

# Answer
> 4 votes
## Python, 123 characters

```
N=[10]+map(int,raw_input().split())
for y in range(10):print''.join((2*n*' '+'/'+2*y*'-'+'\ ')[-2*n-1:-1]for n in N)[9-y:]

```

# Answer
> 2 votes
## Perl, 130 126 132 chars

```
$_=<>;$s=" "x9;map{$k.="/\\"."  "x($_-1)if$_}split;$_="$s$k/\\$s\n";for$i(0..9){print;s%\\-%-\\%g;s%\\/%-\\%g;s%\\ %-\\%g;s% /%/-%g}

```

Slightly shorter version which takes input as command-line arguments rather than from stdin:

```
$s=" "x9;map{$k.="/\\"."  "x($_-1)if$_}@ARGV;$_="$s$k/\\$s\n";for$i(0..9){print;s%\\-%-\\%g;s%\\/%-\\%g;s%\\ %-\\%g;s% /%/-%g}

```

Can't believe no-one did a regex solution yet. Perl is a long way from being my best language, so this can probably lose a lot more. I'd be interested to see a sed implementation, if someone's up for the challenge.

(Thanks, @mbx, for 4 chars).

# Answer
> 1 votes
## JavaScript, 396 bytes

```
function p(a){for(u=0;u<10;u++){t[u+a][9-u]="/";for(k=9-u+1+a;k<10+u+a;k++)t[k][u]="-";
t[10+u+a][u]="\\"}}function _(a){t=[];for(i=0;i<50;i++){t[i]=[];for(j=0;j<10;j++)t[i][j]=" "
}var a=a.split(" "),b=a.reduce(function(a,b){return a-0+(b-0)})*2;for(i=a.length-1;i>=0;
i--)p(b),b-=a[i]*2-0;p(0);a="";for(j=0;j<10;j++){b="";for(i=0;i<50;i++)b+=t[i][j];
a+=b.replace(/\s+$/,"")+(j<9?"\n":"")}return a}

```

I'm not going to win with JavaScript, but there is a JavaScript entry now :)

Usage: `_("1 2 3")` etc.

# Answer
> 1 votes
## Ruby (112)

Slightly shorter than Ventero's Ruby solution, with a different approach. I just started learning Ruby, so this can probably be reduced quite a bit.

```
s=' '*9+r='/\\';gets.split.map{|i|s+=' '*2*(i.to_i-1)+r}
10.times{puts s;s.gsub!' /','/-';s.gsub!(/\\.?/,'-\\')}

```

# Answer
> 1 votes
# Powershell, ~~105~~ 98 bytes, the strictest reading of the spec

*-7 bytes from migimaru's answer.*

```
($a=' '+-join(,5+$args-gt0|%{'  '*--$_+'/\'}))
1..9|%{($a=$a-replace' /','/-'-replace'\\.?','-\')}

```

Test script:

```
$f = {

($a=' '+-join(,5+$args-gt0|%{'  '*--$_+'/\'}))
1..9|%{($a=$a-replace' /','/-'-replace'\\.?','-\')}

}

@(
,(@"
         /\
        /--\
       /----\
      /------\
     /--------\
    /----------\
   /------------\
  /--------------\
 /----------------\
/------------------\
"@)

,(@"
         /\      /\    /\/\
        /--\    /--\  /--\-\
       /----\  /----\/----\-\
      /------\/------\-----\-\
     /--------\-------\-----\-\
    /----------\-------\-----\-\
   /------------\-------\-----\-\
  /--------------\-------\-----\-\
 /----------------\-------\-----\-\
/------------------\-------\-----\-\
"@, 4,3,1)

,(@"
         /\                /\
        /--\              /--\
       /----\            /----\
      /------\          /------\
     /--------\        /--------\
    /----------\      /----------\
   /------------\    /------------\
  /--------------\  /--------------\
 /----------------\/----------------\
/------------------\-----------------\
"@, 0,9)

,(@"
         /\                    /\
        /--\                  /--\
       /----\                /----\
      /------\              /------\
     /--------\            /--------\
    /----------\          /----------\
   /------------\        /------------\
  /--------------\      /--------------\
 /----------------\    /----------------\
/------------------\  /------------------\
"@, 11)
) | % {
    $expected, $a = $_
    $result = &$f @a
    ($result-join"`n")-eq$expected
    $result
}

```

Output:

```
True
         /\
        /--\
       /----\
      /------\
     /--------\
    /----------\
   /------------\
  /--------------\
 /----------------\
/------------------\
True
         /\      /\    /\/\
        /--\    /--\  /--\-\
       /----\  /----\/----\-\
      /------\/------\-----\-\
     /--------\-------\-----\-\
    /----------\-------\-----\-\
   /------------\-------\-----\-\
  /--------------\-------\-----\-\
 /----------------\-------\-----\-\
/------------------\-------\-----\-\
True
         /\                /\
        /--\              /--\
       /----\            /----\
      /------\          /------\
     /--------\        /--------\
    /----------\      /----------\
   /------------\    /------------\
  /--------------\  /--------------\
 /----------------\/----------------\
/------------------\-----------------\
True
         /\                    /\
        /--\                  /--\
       /----\                /----\
      /------\              /------\
     /--------\            /--------\
    /----------\          /----------\
   /------------\        /------------\
  /--------------\      /--------------\
 /----------------\    /----------------\
/------------------\  /------------------\

```

# Powershell, ~~101~~ 94, fun with one leading whitespace

```
($a=-join(,6+$args-gt0|%{'  '*--$_+'/\'}))
1..9|%{($a=$a-replace' /','/-'-replace'\\.?','-\')}

```

# Answer
> 0 votes
I couldn't get the C#3 version any shorter than this. I don't know the character count exactly, but I suspect that I have lost. :-(

```
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace PyramidRenderer
{
    /// <summary>
    /// Generates ASCII-art pyramids at user-specified horizontal locations to
    /// the standard output stream.
    /// </summary>
    public class Program
    {
        /// <summary>
        /// Generates one or more ASCII-art pyramids at the locations specified and
        /// sends them to the standard output stream.
        /// </summary>
        /// <param name="args">The command-line arguments. These should be non-negative
        /// integers that specify the horizontal distance of each additional pyramid from the
        /// preceeding pyramid. Whether or not any distances are suppplied, a pyramid
        /// is rendered at the starting location.</param>
        public static void Main(string[] args)
        {
            try
            {
                AppDomain.CurrentDomain.UnhandledException += new UnhandledExceptionEventHandler(CurrentDomain_UnhandledException);

                int[] pyramidDistances = ParsePyramidLocationsFromCommandLine(args).ToArray();
                PyramidCollection pyramids = new PyramidCollection(pyramidDistances);
                pyramids.RenderToText(Console.Out);
            }
            catch (ArgumentException ex)
            {
                Console.Error.WriteLine(ex.Message);
            }
        }

        /// <summary>
        /// Handler for the unhandled exception. This just displays the error message to
        /// the standard error stream.
        /// </summary>
        /// <param name="sender">Required but unnecessary sender object for the event handler.</param>
        /// <param name="e">The object that represents the exception.</param>
        private static void CurrentDomain_UnhandledException(object sender, UnhandledExceptionEventArgs e)
        {
            Debug.Assert(e.ExceptionObject != null);

            string exceptionText;
            Exception ex = e.ExceptionObject as Exception;
            if (ex == null)
                exceptionText = e.ExceptionObject.ToString();
            else
                exceptionText = ex.Message;
            Console.Error.WriteLine(exceptionText);
        }

        /// <summary>
        /// Takes the command-line arguments and converts them to a sequence of
        /// non-negative integers.
        /// </summary>
        /// <param name="args">The command-line arguments as supplied to Main.</param>
        /// <returns>A sequence of integers that represent the user’s distance selections.</returns>
        /// <exception cref="ArgumentException">An invalid argument was supplied.</exception>
        private static IEnumerable<int> ParsePyramidLocationsFromCommandLine(string[] args)
        {
            Debug.Assert(args != null);

            foreach (string arg in args)
            {
                int result;
                if (int.TryParse(arg, out result))
                {
                    if (result < 0)
                        throw new ArgumentException(string.Format("Invalid distance specified: {0}", arg));

                    yield return result;
                }
                else
                {
                    throw new ArgumentException(string.Format("Invalid option: {0}", arg));
                }
            }
        }
    }

    /// <summary>
    /// Represents a single pyramid to be rendered.
    /// </summary>
    internal class Pyramid
    {
        /// <summary>
        /// The height of the pyramids in text rows. The width of each pyramid will be
        /// twice the height.
        /// </summary>
        internal const int Height = 10;

        /// <summary>
        /// The length in characters of the horizontal unit distance in which the user
        /// specifies the pyramid distances.
        /// </summary>
        internal const int PyramidUnits = 2;

        /// <summary>
        /// The character to output as the background of the pyramids.
        /// </summary>
        private const char backgroundChar = ' ';

        /// <summary>
        /// The character to output as the left edge of the pyramids.
        /// </summary>
        private const char leftEdgeChar = '/';

        /// <summary>
        /// The character to output within each pyramid, between the edges.
        /// </summary>
        private const char brickChar = '-';

        /// <summary>
        /// The character to output as the right edge of the pyramids.
        /// </summary>
        private const char rightEdgeChar = '\\';

        /// <summary>
        /// The absolute horizonal location of the pyramid’s bottom left corner as
        /// specified in PyramidUnits.
        /// </summary>
        private int position;

        /// <summary>
        /// Constructs a new pyramid object at the specified location.
        /// </summary>
        /// <param name="position">The absolute horizonal location of the pyramid’s bottom
        /// left corner in PyramidUnits.</param>
        internal Pyramid(int position)
        {
            Debug.Assert(position >= 0);

            this.position = position;
        }

        /// <summary>
        /// Renders a single row the pyramid to the supplied text stream starting at
        /// the indicated location.
        /// </summary>
        /// <param name="textWriter">The output stream to which the pyramid is to
        /// be rendered.</param>
        /// <param name="row">The row of the pyramid to render. Zero is the top row,
        /// and Height - 1 is the bottom row.</param>
        /// <param name="startingPosition">The text character position—indexed at zero—at
        /// which the rendering is to begin. If non-zero, this identifies the column one
        /// past the ending location of the previous pyramid.</param>
        /// <returns>The horizontal location (in characters) at which the next item
        /// may be rendered.</returns>
        internal int RenderRow(TextWriter textWriter, int row, int startingPosition)
        {
            Debug.Assert(textWriter != null);
            Debug.Assert(row >= 0);
            Debug.Assert(startingPosition >= 0);

            int leftBoundary = Height - 1 - row + position * PyramidUnits;
            int rightBoundary = Height + row + position * PyramidUnits;

            startingPosition = RenderField(textWriter, backgroundChar, startingPosition, leftBoundary);
            startingPosition = RenderField(textWriter, leftEdgeChar, startingPosition, leftBoundary + 1);
            startingPosition = RenderField(textWriter, brickChar, startingPosition, rightBoundary);
            startingPosition = RenderField(textWriter, rightEdgeChar, startingPosition, rightBoundary + 1);
            return startingPosition;
        }

        /// <summary>
        /// Outputs a sequence of repeated characters from the indicated starting position to
        /// just before the ending position, unless the starting position is already equal to
        /// or greater than the ending position.
        /// </summary>
        /// <param name="textWriter">The output stream to which the field is to be rendered.</param>
        /// <param name="character">The character to be repeated in the output.</param>
        /// <param name="startingPosition">The location at which rendering may begin in
        /// characters indexed at zero.</param>
        /// <param name="endingPosition">The location one past the location at which rendering
        /// is to end.</param>
        /// <returns>The position at which the next field may begin.</returns>
        private static int RenderField(TextWriter textWriter, char character, int startingPosition, int endingPosition)
        {
            Debug.Assert(textWriter != null);
            Debug.Assert(startingPosition >= 0);
            Debug.Assert(endingPosition >= 0);

            int charCount = endingPosition - startingPosition;
            if (charCount <= 0)
                return startingPosition;
            textWriter.Write(new string(character, charCount));
            return endingPosition;
        }
    }

    /// <summary>
    /// A collection of pyramids to be displayed.
    /// </summary>
    internal class PyramidCollection
    {
        /// <summary>
        /// A left-to-right ordered list of the pyramids that the user has
        /// requested to be rendered.
        /// </summary>
        List<Pyramid> allPyramids = new List<Pyramid>();

        /// <summary>
        /// Constructs a new pyramid collection.
        /// </summary>
        /// <param name="distances">The distances of each non-leftmost pyramid (in PyramidUnits) after
        /// the previous pyramid. The total number of pyramids will be one greater than the length of
        /// the distances array.</param>
        internal PyramidCollection(int[] distances)
        {
            Debug.Assert(distances != null);

            int nextPosition = 0;
            allPyramids.Add(new Pyramid(nextPosition));
            foreach (int nextDistance in distances)
            {
                Debug.Assert(nextDistance >= 0);

                try
                {
                    checked
                    {
                        nextPosition += nextDistance;
                        int endLocation = nextPosition * Pyramid.PyramidUnits + Pyramid.Height * 2;
                    }
                }
                catch (OverflowException)
                {
                    // Ignore any pyramids specified beyond the integer maximum distance.
                    break;
                }
                allPyramids.Add(new Pyramid(nextPosition));
            }
        }

        /// <summary>
        /// Outputs ASCII-art images of the pyramids in this collection to the
        /// provided output stream.
        /// </summary>
        /// <param name="textWriter">The output stream to which the pyramids
        /// are to be rendered.</param>
        internal void RenderToText(TextWriter textWriter)
        {
            Debug.Assert(textWriter != null);

            for (int row = 0; row < Pyramid.Height; row++)
            {
                int startingPosition = 0;
                foreach (Pyramid pyramid in allPyramids)
                {
                    startingPosition = pyramid.RenderRow(textWriter, row, startingPosition);
                }
                textWriter.WriteLine();
            }
        }
    }

}

```

---
Tags: code-golf, ascii-art
---


title: How many moves?

text:
# Question
Title: How many moves?
Given two different positions on a chess board and the type of piece, output the minimum number of moves it will take for that piece to go from one position to another.

### Rules

The given piece can be King,Queen,Rook,Knight and Bishop. (This input can be taken as any 5 unique characters)

The 2 positions can be taken in any convenient format,

```
Example:
a8 b8 c8 d8 ... h8
a7 b7 c7 d7 ... h7
...
...
a1 b1 c1 d1 ... h1

```

In case the piece cannot reach there, output anything other than a positive integer.

### Examples

```
i/p ---- o/p
King
a1,a4    3
a1,h6    7
b3,h5    6

Queen
a1,a4    1
a1,h6    2
b3,f7    1

Rook
a1,a4    1
a1,h6    2
h2,c7    2

Knight
a1,a4    3
a1,h6    4
b2,d3    1
b2,c3    2
b3,c3    3
a1,b2    4

Bishop
a1,a4    -1
a1,h6    2
b2,d3    -1
e1,h4    1

```

# Answer
> 9 votes
# JavaScript (Node.js), ~~183~~ ~~180~~ 179 bytes

```
with(Math)(a,b,c,d,t,x=abs(a-c),y=abs(b-d),v=x<y?y:x,q=0|.9+max(/[18][18]/.test(a+b+9+c+d)-v?x/2:3,y/2,x*y?x*y-4?(x+y)/3:3:2))=>t?t==2&x+y?0:t&1>x*y|t/2&x==y?1:t<4?2:v:q+(q+x+y&1)

```

Try it online!

So long for edge case, thank Arnauld for checking. Knight test

# Answer
> 8 votes
# APL (Dyalog Classic), ~~117~~ ~~107~~ ~~105~~ ~~103~~ ~~98~~ ~~97~~ ~~95~~ ~~92~~ ~~89~~ 87 bytes

```
{(⍎⍺⊃'⌈/' '≢∘∪~∘0' '+/×' '{⍺∊⍵:0⋄1+⍺∇i/⍨∨⌿2=|×/↑⍵∘.-i←,⍳8 8}/,¨⊂¨↓⍵' '≢∘∪×2=.|⊢')⊣|-⌿⍵}

```

Try it online!

left arg is piece type: 0=king, 1=queen, 2=rook, 3=knight, 4=bishop; right arg is a 2x2 matrix of coords, each row representing a position; returns 0 for unreachable

`|-⌿⍵` computes the pair \[abs(∆x),abs(∆y)\]

`(⍎⍺⊃`...`)⊣` chooses an expression from the "..." list; if it's a function, it's applied to `|-⌿⍵`; if it's a value (this happens only for a knight),  makes sure to return it instead of `|-⌿⍵`

* king: max (`⌈/`) of the abs ∆-s
* queen: remove zeroes (`~∘0`) and count () unique ()
* rook: sum (`+/`) of signa (monadic `×`; 0 for 0, 1 for positive)
* knight: `{⍺∊⍵:0⋄1+⍺∇i/⍨∨⌿2=|×/↑⍵∘.-i←,⍳8 8}/,¨⊂¨↓⍵` \- start with the initial position and recursively compute generations of knight moves until the final position is in the set; return recursion depth
* bishop: are the parities of the two ∆-s equal? (`2=.|⊢`, equivalent to `=/2|⊢`) multiply the boolean result (0 or 1) by the count-unique (`≢∘∪`)

# Answer
> 2 votes
# Java (JDK), 229 bytes

```
(p,a,b,c,d)->{c^=a/4*7;a^=a/4*7;d^=b/4*7;b^=b/4*7;int x=c<a?a-c:c-a,y=d<b?b-d:d-b,z=(x^=y^(y=y<x?y:x))-y;return p<1?x:p<2?z*y<1?1:2:p<3?2-z%2:p<4?x+y<2?3:(a<c?a+b:c+d)+x<2|x==2&z<1?4:z+2*Math.ceil((y-z)/(y>z?3:4.)):z<1?1:~z*2&2;}

```

Try it online!

## Explanations

* The board is a 0-based board.
* The returned-value is an integer, represented as a double. There will never be any decimal part.

**Code:**

```
(p,a,b,c,d)->{                          // double-returning lambda.
                                        // p is the piece-type (0: king, 1: queen, 2: rook, 3: knight, 4: bishop)
                                        // a is the origin-X
                                        // b is the origin-Y
                                        // c is the destination-X
                                        // d is the destination-Y
 c^=a/4*7;a^=a/4*7;                     // Mirror board if origin is in the top part of the board
 d^=b/4*7;b^=b/4*7;                     // Mirror board if origin is in the left part of the board
 int x=c<a?a-c:c-a,                     // x is the X-distance between a and c
     y=d<b?b-d:d-b,                     // y is the Y-distance between b and d
     z=(x^=y^(y=y<x?y:x))-y;            // z is the delta between x and y
                                        // also, swap x and y if necessary so that x is the greater value.
               //    At this point,
               //     x      cannot be 0 (because the two positions are different)
               //     z<1    means the origin and destination are on the same diagonal
               //     y<1    means the origin and destination are on the same horizontal/vertical line
 return
  p<1?x:                                //  For a king, just take the max distance.
  p<2?z*y<1?1:2:                        //  For a queen, just move once if in direct line, or twice.
  p<3?2-z%2:                            //  For a rook, just move once if on the same horizontal or vertical line, or twice
  p<4?                                  //  For a knight,
   x+y<2?3:                             //   Hardcode 3 if moving to the next horizontal/vertical square
   (a<c?a+b:c+d)+x<2|x==2&z<1?4:        //   Hardcode 4 if moving 2 cases in diagonal or one case in diagonal in a corner.
   z+2*Math.ceil((y-z)/(y>z?3:4.)):     //   Compute the number of moves necessary for the usual cases
  z<1?1:                                //  For a bishop, hardcode 1 if they are on the same diagonal
   ~z*2&2;                              //   Return 2 if they have the same parity else 0.
}

```

## Credits

* -2 bytes thanks to Arnauld, as well as for making me realize that I had an issue with all my corner-cases.

# Answer
> 2 votes
# Japt, 67 bytes

```
®ra
g[_rw}_â è}@=ã ü;@pUÌïVõ á ÈíaY})Ìde[TT]}a Ä}_è}_ra v *Zâ l}]gV

```

Try it online!

That was quite an experience. I took a lot of inspiration from the excellent APL Answer. I suspect there is a lot of golfing still possible especially in the Knight code.

The positions are the first input, in the form `[[x1,x2],[y1,y2]]`. It should work fine on `[[y1,y2],[x1,x2]]` as well. Piece selection is the second input, with 0=king, 1=queen, 2=knight, 3=rook, 4=bishop. Note that Knight and Rook are swapped compared to the APL answer.

Explanation:

```
®ra         :Turn absolute positions into relative movement and store in U
®           : For each of X and Y
 ra         : Get the absolute difference between the start position and the end position

g[...]gV    :Apply the appropriate function
 [...]      : A list of functions
      gV    : Get the one indicated by the second input
g           : Apply it to U

_rw}        :King function
 rw         : Get the maximum of X and Y

_â è}       :Queen function
 â          : Get unique elements
   è        : Count non-zero elements

@=ã ü;@pUÌï2õ á ÈíaY})Ìde[TT]}a Ä}  :Knight function
 =ã ü;                              : Wrap U twice (U -> [[U]])
      @                      }a Ä   : Repeat until True; return number of tries:
        UÌ                          :  Get the previous positions
          ï                         :  Cartesian product with:
           2õ                       :   The range [1,2]
              á                     :   All permutations, i.e. [[1,2],[2,1]]
                ÈíaY})              :  Apply each move to each position
       p                            :  Store the new positions
                      Ìde[TT]       :  True if any are at the destination

_è}         :Rook function
 è          : Count non-zero elements

_ra v *Zâ l}    :Bishop function
 ra             : Absolute difference between X and Y
    v           : Is divisible by 2? (returns 1 or 0)
      *         : Times:
       Zâ       :  Get the unique elements
          l     :  Count them

```

# Answer
> 1 votes
# Charcoal, 108 bytes

```
Ｆ…β⁸Ｆ⁸⊞υ⁺ι⊕κ≔⟦⟦η⟧⟧δＷ¬№§δ±¹ζ⊞δΦυΦ§δ±¹⁼⁵ΣＥμＸ⁻℅ξ℅§κπ²≔Ｅη↔⁻℅ι℅§ζκε≡θKＩ⌈εQＩ∨∨¬⌊ε⁼⊟ε⊟ε²RＩ∨¬⌊ε²BＩ∧¬﹪Σε²∨⁼⊟ε⊟ε²NＩ⊖Ｌδ

```

Try it online! Link is to verbose version of code. Explanation:

```
Ｆ…β⁸Ｆ⁸⊞υ⁺ι⊕κ

```

List all the 64 squares of the board into the predefined empty list variable.

```
≔⟦⟦η⟧⟧δ

```

Make a list of lists whose first entry is a list containing the start position.

```
Ｗ¬№§δ±¹ζ

```

Repeat until the last entry of the list contains the end position.

```
⊞δΦυΦ§δ±¹⁼⁵ΣＥμＸ⁻℅ξ℅§κπ²

```

Filter all the board positions that are a knight's move away from any entry in the last entry of the list of lists and push that list to the list of lists. This includes positions previously visited but we weren't interested in them anyway, so we end up with a breadth first search of the board for the end position.

```
≔Ｅη↔⁻℅ι℅§ζκε

```

Calculate the absolute coordinate differences between the start and end positions.

```
≡θ

```

Select based on the input piece.

```
KＩ⌈ε

```

If it's a king then print the maximum absolute coordinate difference.

```
QＩ∨∨¬⌊ε⁼⊟ε⊟ε²

```

If it's a queen then print 2 unless the two differences are equal or one is zero.

```
RＩ∨¬⌊ε²

```

If it's a rook then print 2 unless one of the differences is zero.

```
BＩ∧¬﹪Σε²∨⁼⊟ε⊟ε²

```

If it's a bishop then print 0 if the squares are of opposite parity otherwise print 2 unless the two differences are equal.

```
NＩ⊖Ｌδ

```

If it's a knight then print the number of loops taken to find the end position.

---
Tags: code-golf, chess
---