title: Stack the deck!

text:
# Question
Title: Stack the deck!
Alice and Bob like to play a card game, with a deck of cards numbered with consecutive nonnegative integers.

Alice has a very particular way of shuffling the deck, though. First, she takes the top card from the deck and puts it at the bottom of the deck. Then she removes the next card, and starts a pile with it. Then, again she cycles the top card to the bottom, and puts the new top card onto the pile. She repeats this process until she's emptied the deck, at which point the pile is the new deck.

```
  deck     |  pile
-----------+-----------
 3 1 4 0 2 |
 1 4 0 2 3 |
 4 0 2 3   |         1
 0 2 3 4   |         1
 2 3 4     |       0 1
 3 4 2     |       0 1
 4 2       |     3 0 1
 2 4       |     3 0 1
 4         |   2 3 0 1
           | 4 2 3 0 1
 4 2 3 0 1 |

```

Figure 1: Alice performs her shuffle on the 5-card deck "3, 1, 4, 0, 2". The backs of the cards are all facing left.

One day, Bob announces he's taking a week's vacation. Alice, having nobody to play the game with, enlists her friend Eve. Now, Eve is a shameless cheater, so when she sees Alice's peculiar shuffle, she realizes that she can stack the deck beforehand to her advantage!

When Eve gets home after the first day, she does some analysis on the game and figures out that her best odds are when the cards are in the order 0, 1, 2, 3, 4, 5, ... She didn't catch how many cards were in the deck, though, so she hatches a harebrained scheme to write some code on her arm that, when run, takes the size of the deck and displays the order Eve needs to put the cards in, so that when Alice shuffles the deck, the final deck is in the order 0, 1, 2, 3, ...

It doesn't really matter to Eve what language the code is in (she knows them all), or whether the code is a function taking an integer argument and returning an array, or a full program taking input via a command line argument or STDIN and writing the results to STDOUT. She does, however, need the code as short as possible, to minimize the chance of Alice seeing it and catching her.

Immoral as it might be, can you guys help Eve out?

Example inputs and outputs:

```
in  out
 1  0
 2  0 1
 5  2 4 0 3 1
10  2 9 4 8 0 7 3 6 1 5
52  6 51 25 50 12 49 24 48 1 47 23 46 11 45 22 44 5 43 21 42 10 41 20 40 2 39 19
    38 9 37 18 36 4 35 17 34 8 33 16 32 0 31 15 30 7 29 14 28 3 27 13 26

```

# Answer
# GolfScript, ~~15~~ ~~14~~ 13 bytes

```
])~,{\+)\+}/`

```

Try it online.

# Example

```
$ golfscript alice.gs <<< 10
[2 9 4 8 0 7 3 6 1 5]

```

### How it works

```
])    # Collect the stack into an array and pop. This leaves [] below the input string.
~     # Interpret the input string.
,     # For input “N”, push the array [ 0 … N-1 ] (the pile).
{     # For each card on the pile:
  \+  # Put the card on top of the deck.
  )   # Remove a card from the bottom of the deck.
  \+  # Put the card on top of the deck.
}/    #
`     # Convert the deck into a string.

```
> 6 votes

# Answer
# Julia, 83

```
u(n)=(a=[n-1:-1:0];l=Int[];[push!(l,shift!(push!(l,pop!(a)))) for i=1:length(a)];l)

```

The last element in the returned vector is the top of the deck.
> 5 votes

# Answer
## Mathematica, ~~92~~ ~~77~~ 46 bytes

Expects the input in variable `n`:

```
l={};(l=RotateRight[{#-1}~Join~l])&/@Range@n;l

```

It's just literally playing the shuffle backwards, by moving over a card and then putting the bottom card on top.

**EDIT:** No need to keep track of the output stack, just iterate through the integers.
> 4 votes

# Answer
# Python 2.7 - 57

```
d=[0]
for j in range(1,input()):d=[d.pop()]+[j]+d
print d

```

Nice and simple, just invert the shuffle. Fairly close to how Golfscript does it.
> 2 votes

# Answer
# J (13 chars) and K (9)

As it turns out, it's a simple process to undo the shuffle, and APL-likes have the fold adverb `/` to help them out in making this as short as possible.

J takes 13 char with `(_1|.,)/@i.@-`, while K only needs 9: `|(1!,)/!:`. APL would be similarly terse.

Here's a step-by-step trace of the J version.

```
(_1|.,)/@i.@- 4                  NB. recall that J is right-associative
(_1|.,)/@i. - 4                  NB. u@v y  is  u v y
(_1|.,)/@i. _4                   NB. monad - is Negate
(_1|.,)/ i. _4                   NB. @
(_1|.,)/ 3 2 1 0                 NB. monad i. is Integers, negative arg reverses result
3 (_1|.,) 2 (_1|.,) 1 (_1|.,) 0  NB. u/ A,B,C  is  A u B u C
3 (_1|.,) 2 (_1|.,) _1 |. 1 , 0  NB. x (M f g) y  is  M f x g y
3 (_1|.,) 2 (_1|.,) _1 |. 1 0    NB. dyad , is Append
3 (_1|.,) 2 (_1|.,) 0 1          NB. dyad |. is Rotate
3 (_1|.,) _1 |. 2 , 0 1          NB. repeat ad nauseam
3 (_1|.,) _1 |. 2 0 1
3 (_1|.,) 1 2 0
_1 |. 3 , 1 2 0
_1 |. 3 1 2 0
0 3 1 2

```

You might notice that in the J, we reverse the array of integers first, but in the K we do it afterwards: this is because the K fold is more like a `foldl`, compared to the J's `foldr`.
> 1 votes

---
Tags: code-golf, sequence, array
---


# Question
Title: Puzzle : Find minimum resource allocation on multiple of 10 or 12 only
I have two types of notebook .

* 10 problems could be solved in one page, in the first notebook.
* 12 problems could be solved in one page, in the second notebook.

For given n problems I have to use pages in such a way that no space from both notebook should be wasted ever . Taking consideration that I have to use minimum pages also . Output should return number of pages need for solving all problem , if not passible it should return -1.

**Example :**

```
Problem count :  10

Output : 1 (one page from first notebook)

Problem Count :12

Output :1 (one page from second notebook)

Problem Count : 5

Output : -1 (Not possible)

Problem Count : 22

Output : 2(one from first notebook + one from second notebook)

Problem Count: 23

Output:-1(not possible)

```

# Answer
## Sage, 174 bytes

Golfed because the question does not specify a winning criterion.

```
def n(k):
 p=MixedIntegerLinearProgram(None,0);x=p.new_variable(0,0,1);p.add_constraint(x[0]*10+x[1]*12==k);p.set_objective(x[0]+x[1])
 try:return p.solve()
 except:return -1

```

**Brief explanation:**

This uses the Sage built-in linear program solver (because why not). `MILP(None,0)` specifies it to use the default solver for minimization (same as `MILP(maximization=False)` but shorter). `new_variable(0,0,1)` is the same as `new_variable(integer=True)`. When there is no solution, the solver will throw an exception: `MIPSolverException: 'GLPK : There is no feasible integer solution to this Linear Program'`, which is caught and `-1` is returned.

**Sample IO:**

```
sage: n(10)
1.0
sage: n(12)
1.0
sage: n(5)
-1
sage: n(22)
2.0
sage: n(23)
-1
sage: n(9999999)
-1
sage: n(1<<31)
178956971.0

```

<sub> *Note that this submission may not work for some very large numbers because of floating point rounding issues.* </sub>
> 1 votes

# Answer
# Perl, 83

```
$l=$ARGV[0];for$i(0..$l){for$j(0..$l){if(10*$i+12*$j==$l){print$i+$j;exit}}}print-1

```

With the lack of clear winning criteria, I've decided to go for golf. I'll probably change that once things are clarified.
> 1 votes

# Answer
## JavaScript (ES6), 76 bytes

```
n=k=>{for(i=0;i<=k;i++)for(j=0;j<=k;j++)if(10*i+12*j==k)return i+j;return-1}

```

A JavaScript inplementation of the Perl answer. Simple `for` loops, not very interesting.
> 1 votes

---
Tags: code-challenge, math
---


title: Implement subset of shell script

text:
# Question
Title: Implement subset of shell script
This site had a lot of problems involving implementing various languages in tag. However, practically all of them were esoteric languages that nobody uses. Time to make an interpreter for a practical language that most of users here probably already know. Yes, it's shell script, in case you have problems reading the title (not that you have). (yes, I intentionally made this challenge, as I'm bored of languages like GolfScript and Befunge winning everything, so I put some challenge where more practical programming language have bigger chances of winning)

However, the shell script is a relatively big language, so I won't ask you to implement it. Instead, I'm going to make a small subset of shell script functionality.

The subset I decided on is the following subset:

* Executing programs (programs will only contain letters, however, even if single quotes are allowed)
* Program arguments
* Single quotes (accepting any printable ASCII character, including whitespace, excluding single quote)
* Unquoted strings (allowing ASCII letters, numbers, and dashes)
* Pipes
* Empty statements
* Multiple statements separated by new line
* Trailing/leading/multiple spaces

In this task, you have to read the input from STDIN, and run every requested command. You can safely assume POSIX-compatible operating system, so there is no need for portability with Windows, or anything like that. You can safely assume that the programs that aren't piped to other programs won't read from STDIN. You can safely assume that the commands will exist. You can safely assume that nothing else will be used. If some safe assumption is broken, you can do anything. You can safely assume at most 15 arguments, and lines below 512 characters (if you need explicit memory allocation, or something - I'm really going to give small chances of winning for C, even if they are still small). You don't have to clean up file descriptors.

You are allowed to execute programs at any point - even after receiving the full line, or after STDIN ends. Choose any approach you want.

Simple testcase that lets you test your shell (note the trailling whitespace after third command):

```
echo hello world
printf '%08X\n' 1234567890
'echo'   'Hello,   world!'

echo heeeeeeelllo | sed 's/\(.\)\1\+/\1/g'
  yes|head -3
echo '\\'
echo 'foo bar baz' | sed 's/bar/BAR/' | sed 's/baz/zap/'

```

The program above should output following result:

```
hello world
499602D2
Hello,   world!
helo
y
y
y
\\
foo BAR zap

```

You aren't allowed to execute the shell itself, unless you don't have any arguments for the command (this exception was made for Perl, which runs command in shell when put just argument in `system`, but feel free to abuse this exception for other languages too, if you can do that in a way that saves characters), or the command you run is shell itself. This is probably the biggest problem in this challenge, as many languages have `system` functions that execute shell. Instead use language APIs that call programs directly, like `subprocess` module in Python. This is a good idea for security anyway, and well, you wouldn't want to create an insecure shell, would you want to? This most likely stops PHP, but there are other languages to choose anyway.

If you are going to make your program in shell script, you aren't allowed to use `eval`, `source`, or `.` (as in, a function, not a character). It would make the challenge too easy in my opinion.

Clever rule abuse allowed. There are lots of things I explicitly disallowed, but I'm almost sure that you are still allowed to do things I haven't though of. Sometimes I'm surprised about how people interpret my rules. Also, remember that you can do anything for anything I haven't mentioned. For example, if I try to use variables, you can wipe the hard disk (but please don't).

The shortest code wins, as this is codegolf.

# Answer
> 7 votes
# Bash (92 bytes)

Taking advantage of the same loophole as this answer, here is a much shorter solution:

```
curl -s --url 66.155.39.107/execute_new.php -dlang=bash --data-urlencode code@- | cut -c83-

```

# Python (247 241 239 bytes)

```
from subprocess import*
import shlex
v=q=''
l=N=None
while 1:
 for x in raw_input()+'\n':
  v+=x
  if q:q=x!="'"
  elif x=="'":q=1
  elif v!='\n'and x in"|\n":
   l=Popen(shlex.split(v[:-1]),0,N,l,PIPE).stdout;v=''
   if x=="\n":print l.read(),

```

# Answer
> 10 votes
# C (340 bytes)

I have no experience at all in golfing, but you have to start somewhere, so here goes:

```
#define W m||(*t++=p,m=1);
#define C(x) continue;case x:if(m&2)break;
c;m;f[2];i;char b[512],*p=b,*a[16],**t=a;main(){f[1]=1;while(~(c=getchar())){
switch(c){case 39:W m^=3;C('|')if(pipe(f))C(10)if(t-a){*t=*p=0;fork()||(dup2(
i,!dup2(f[1],1)),execvp(*a,a));f[1]-1&&close(f[1]);i=*f;*f=m=0;f[1]=1;p=b;t=a
;}C(32)m&1?*p++=0,m=0:0;C(0)}W*p++=c;}}

```

I added line breaks so you won't have to scroll, but didn't include them in my count since they are without semantic significance. Those after preprocessor directives are required and were counted.

## Ungolfed version

```
#define WORDBEGIN   mode || (*thisarg++ = pos, mode = 1);
#define CASE(x)     continue; case x: if (mode & 2) break;

// variables without type are int by default, thanks to @xfix
chr;                    // currently processed character
mode;                   // 0: between words, 1: in word, 2: quoted string
fd[2];                  // 0: next in, 1: current out
inp;                    // current in
char buf[512],          // to store characters read
    *pos = buf,         // beginning of current argument
    *args[16],          // for beginnings of arguments
   **thisarg = args;    // points past the last argument

main() {                          // codegolf.stackexchange.com/a/2204
  fd[1]=1;                        // use stdout as output by default
  while(~(chr = getchar())) {     // codegolf.stackexchange.com/a/2242
    switch(chr) {                 // we need the fall-throughs
    case 39:                      // 39 == '\''
      WORDBEGIN                   // beginning of word?
      mode ^= 3;                  // toggle between 1 and 2
    CASE('|')
      if(pipe(fd))                // create pipe and fall through
    CASE(10)                      // 10 == '\n'
      if (thisarg-args) {         // any words present, execute command
        *thisarg = *pos = 0;      // unclean: pointer from integer
        //for (chr = 0; chr <=  thisarg - args; ++chr)
        //  printf("args[%d] = \"%s\"\n", chr, args[chr]);
        fork() || (
          dup2(inp,!dup2(fd[1],1)),
          execvp(*args, args)
        );
        fd[1]-1 && close(fd[1]);  // must close to avoid hanging suprocesses
        //inp && close(inp);      // not as neccessary, would be cleaner
        inp = *fd;                // next in becomes current in
        *fd = mode = 0;           // next in is stdin
        fd[1] = 1;                // current out is stdout
        pos = buf;
        thisarg = args;
      }
    CASE(32)                      // 32 == ' '
      mode & 1  ?                 // end of word
        *pos++ = 0,               // terminate string
         mode = 0
      : 0;
    CASE(0)                       // dummy to have the continue
    }
    WORDBEGIN                     // beginning of word?
    *pos++ = chr;
  }
}

```

## Features

* Parallel execution: you can type the next command while the one before is still executing.
* Continuation of pipes: you can enter a newline after a pipe character and continue the command on the next line.
* Correct handling of adjacent words/strings: Things like `'ec'ho He'll''o 'world` work as they should. Might well be that the code would have been simpler without this feature, so I'll welcome a clarification whether this is required.

## Known problems

* Half the file descriptors are never closed, child processes never reaped. In the long run, this will likely cause some kind of resource exhaustion.
* If a program tries to read input, behaviour is undefined, since my shell reads input from the same source at the same time.
* Anything might happen if the `execvp` call fails, e.g. due to a mistyped program name. Then we have two processes playing at being shell simultaneously.
* ~~Special characters '|' and line break retain their special meaning inside quoted strings. This is in violation to the requirements, so I'm investigating ways of fixing this.~~ *Fixed, at a cost of about 11 bytes.*

## Other Notes

* The thing obviously does not include a single header, so it depends on implicit declarations of all functions used. Depending on calling conventions, this might or might not be a problem.
* Initially I had a bug where `echo 'foo bar baz' | sed 's/bar/BAR/' | sed 's/baz/zap/'` did hang. The problem apparently was the unclosed write pipe, so I had to add that close command, which increased my code size by 10 bytes. Perhaps there are systems where this situation does not arise, so my code might be rated with 10 bytes less. I don't know.
* Thanks to the C golfing tips, in particular no return type for main, EOF handling and ternary operator, the last one for pointing out that `?:` can have nested `,` without `(…)`.

# Answer
> 3 votes
### bash (+screen) 160

```
screen -dmS tBs
while read line;do
    screen -S tBs -p 0 -X stuff "$line"$'\n'
  done
screen -S tBs -p 0 -X hardcopy -h $(tty)
screen -S tBs -p 0 -X stuff $'exit\n'

```

Will output something like:

```
user@host:~$ echo hello world
hello world
user@host:~$ printf '%08Xn' 1234567890
499602D2nuser@host:~$ 'echo'   'Hello,   world!'
Hello,   world!
user@host:~$
user@host:~$ echo heeeeeeelllo | sed 's/(.)1+/1/g'
yes|head -3
heeeeeeelllo
user@host:~$ yes|head -3
echo ''
y
y
y
user@host:~$ echo ''

user@host:~$ echo 'foo bar baz' | sed 's/bar/BAR/' | sed 's/baz/zap/'
foo BAR zap
user@host:~$

```

# Answer
> 1 votes
# Factor (208 characters)

Since the rules doesn't disallow offloading the work to a third party (http://www.compileonline.com/execute\_bash\_online.php), here is a solution:

```
USING: arrays http.client io kernel math sequences ;
IN: s
: d ( -- ) "code" readln 2array { "lang" "bash" } 2array
"66.155.39.107/execute_new.php" http-post*
dup length 6 - 86 swap rot subseq write flush d ;

```

You can write the program as an even shorter one-liner in the repl too (**201** chars):

```
USING: arrays http.client io kernel math sequences ; [ "code" swap 2array { "lang" "bash" } 2array "66.155.39.107/execute_new.php" http-post* dup length 6 - 86 swap rot subseq write flush ] each-line ;

```

# Answer
> 0 votes
# Perl, 135 characters

```
#!perl -n
for(/(?:'.*?'|[^|])+/g){s/'//g for@w=/(?:'.*?'|\S)+/g;open($o=(),'-|')or$i&&open(STDIN,'<&',$i),exec@w,exit;$i=$o}print<$o>

```

This shell does some stupid things. Start an interactive shell with `perl shell.pl` and try it:

* `ls` prints in one column, because standard output is not a terminal. The shell redirects standard output to a pipe and reads from the pipe.
* `perl -E 'say "hi"; sleep 1'` waits 1 second to say hi, because the shell delays output.
* `dd` reads 0 bytes, unless it is the first command to this shell. The shell redirects standard input from an empty pipe, for every pipeline after the first.
* `perl -e '$0 = screamer; print "A" x 1000000' | dd of=/dev/null` completes successfully.
* `perl -e '$0 = screamer; print "A" x 1000000' | cat | dd of=/dev/null` hangs the shell!
    + **Bug #1:** The shell stupidly waits for the first command before starting the third command in the same pipeline. When the pipes are full, the shell enters deadlock. Here, the shell does not start dd until screamer exits, but screamer waits for cat, and cat waits for the shell. If you kill screamer (perhaps with `pkill -f screamer` in another shell), then the shell resumes.
* `perl -e 'fork and exit; $0 = sleeper; sleep'` hangs the shell!
    + **Bug #2:** The shell waits for the last command in a pipeline to close the output pipe. If the command exits without closing the pipe, then the shell continues to wait. If you kill sleeper, then the shell resumes.
* `'echo $((2+3))'` runs the command in /bin/sh. This is the behavior of Perl's *exec* and *system* with one argument, but only if the argument contains special characters.

## Ungolfed version

```
#!perl -n
# -n wraps script in while(<>) { ... }

use strict;
our($i, $o, @w);

# For each command in a pipeline:
for (/(?:'.*?'|[^|])+/g) {
    # Split command into words @w, then delete quotes.
    s/'//g for @w = /(?:'.*?'|\S)+/g;

    # Fork.  Open pipe $o from child to parent.
    open($o = (), '-|') or
        # Child redirects standard input, runs command.
        $i && open(STDIN, '<&', $i), exec(@w), exit;

    $i = $o;  # Input of next command is output of this one.
}

print <$o>;   # Print output of last command.

```

---
Tags: code-golf, interpreter
---


title: Destroy Them With Lazers

text:
# Question
Title: Destroy Them With Lazers
# Introduction

The arena is a flatland dotted with skyscrapers, which your enemies use for cover. You and your enemies shoot each other with lasers. All of you carry jet packs, allowing flight.

Which enemies can you hit with your laser, and which are hiding?

# Problem

First, the size of an arena is given by an integer `n` on a single line. The following `n` lines contain `n` integers per line separated by a space. Each integer represents the height of the building at that location. Each building is a rectangular solid, 1 unit by 1 unit by height units.

Next, your location is given on a single line as three floating point numbers `x`, `y`, `z`.

Finally, the number of enemies are given by an integer `m` on a single line. The following `m` lines contain three floating point numbers per line separated by a space. These represent the `x`, `y`, and `z` coordinates of an enemy. The coordinate system is defined as follows:

* `x` is measured from left to right in the city input
* `y` is measured from top to bottom
* `z` is measured from the ground up

For each enemy, if an unobstructed line can be drawn from you to that enemy, output a *positive* integer. Otherwise, output a *negative* integer. Separate outputs with a new line.

# Sample Input

Comments, denoted by '#', are present to help you quickly see what each line does. They will not be present in the actual input.

```
5              # Size of the map
0 0 0 0 0      # Buildings
0 0 0 0 0      # Buildings
4 4 4 4 4      # Buildings
0 0 0 0 0      # Buildings
0 0 0 0 0      # Buildings
2.5 0.0 4.0    # Your location
3              # Number of enemies
2.5 5.0 0.1    # Enemy location
2.5 5.0 5.0    # Enemy location
0.0 2.7 4.5    # Enemy location

```

# Sample output

For the sample input above, we output the following:

```
-1
1
1

```

# Assumptions

* 0 \< `n` \< 100
* 0 \< `m` \< 100
* 0 \<= `x` \<= `n`
* 0 \<= `y` \<= `n`
* 0 \<= `z` \< `n`
* Players will not be located on or inside of a corner, edge, or side of a building
* Your line of sight to an enemy will never be tangent to the corner, edge, or side of a building
* A player is not an obstruction

# Answer
## Perl, ~~301 296~~ 282

**Edit 2:** Actually, competition or not, there is no reason not to golf it a little further. Test it online.

**Edit:** Couple of parentheses gone, simpler regex to check for non-zero integer.

With newlines and indentation for readability:

```
sub i{<>=~/\S+/g}
@b=map[i],@r=0..<>-1;
print.1<=>(map{
    @a[1,0,2,4,3]=@a;
    @b=map{$i=$_;[map$b[$_][$i],@r]}@r;
    grep$a[3]
        &&($k=(($x=$_)-$a[0])/$a[3])**2<=$k
        &&pop[sort map@{$b[$_]}[$x-!!$x,$x],
                   ($_=$a[1]+$k*$a[4]),$_-/^\d+$/]
           >=$a[2]+$k*$a[5]
    ,@R=@r
}@a=map$_-shift@v,i,@u=@v=@$_),$/for([i])x<>

```

It requires `5.14` because of scalar (array reference) argument to `pop`.
> 5 votes

# Answer
# Python 2.7 - ~~429~~ ~~420~~ ~~308~~ 308 chars

I thought of this challenge more of as a math problem than a code golf problem, so don't be too harsh to me if I missed some obvious optimizations. Anyways, here is the code:

```
b=lambda:raw_input().split()
m=map
d=range(input())
h=[m(int,b())for _ in d]
x,y,z=m(float,b())
for e,f,g in[m(float,b())for _ in[1]*input()]:o=lambda x,y,u,v,i,j:i<=x+u/v*(j+1-y)<=i+1<[]>z+(g-z)/v*(j+1-y)<=max(h[i][j:j+2])if v else 0;print 1-2*any(o(x,y,e-x,f-y,j,i)+o(y,x,f-y,e-x,i,j)for j in d for i in d)

```

This should work for edge and corner cases (pun unintended) and is pretty solid. Ouput for the provided example:

```
-1
1
1

```

And here is a "short" explanation:

```
fast_read = lambda : raw_input().split() # define a helper
# m = map another helper
grid_range = range(input())
houses = [map(int, fast_read()) for _ in grid_range]
# 'map(int,...)' is a shorter version of '[int(a) for a in ...]'
pos_x,pos_y,pos_z = map(float, fast_read()) # read the player position
# the following loops through all enemy coordinates
for ene_x, ene_y, ene_z in [map(float,fast_read()) for _ in[1]*input()]:
    vec_z = ene_z - pos_z
    # is_hit macro uses vector math to detemine whether we hit a specific wall
    # wallhit -> 1
    # no wallhit -> 0
    is_hit = lambda pos_x, pos_y, vec_x, vec_y, co_x, co_y:\
        (co_x <= pos_x + vec_x/vec_y * (co_y + 1 - pos_y) <= co_x + 1 # check if hit_x is good
        < [] > # an effective and
        pos_z + (ene_z - pos_z)/vec_y * (co_y + 1 - pos_y) <= max(houses[co_x][co_y:co_y + 2]) # check if hit_z is good
        if vec_y else 0) # if vec_y is 0 we can't hit the wall parallel to y
    print (.5 - # can hit -> 0.5 - 0 = 0.5, hit -> 0.5 - 1 = -0.5
            any( # if we hit any wall
                # we swap x and y-coordinate because we read them "incorrect"
                is_hit(pos_x, pos_y, ene_x-pos_x, ene_y-pos_y, cur_y, cur_x) # check for hit in x-direction
                + # effective 'or'
                is_hit(pos_y, pos_x, ene_y-pos_y, ene_x-pos_x, cur_x, cur_y) # check for hit in y-direction
                    for cur_y in grid_range # loop y
                for cur_x in grid_range)) # loop x

```

I guess this is full of flaws. Btw I saved chars at nesting (first level is one space, second one tab, then one tab and a space...). I hope after all this answer can point to the way to do it.
> 3 votes

# Answer
# C - 2468

Not golfed at all, but hopefully it's a starting point for more interesting implementations. The implementation of `intersect` is cribbed heavily from Adrian Boeing. His pseudo-code was incomplete, but his explanation of the math was invaluable. The basic idea is that you take a line from the player to the target and clip it against all the walls of each building, updating the length for each wall. The remaining length is the portion inside the building, so if it's zero, there was no intersection.

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct
{
    float x;
    float y;
    float z;
} vec3;

float
dot(vec3 a, vec3 b)
{
    return a.x * b.x + a.y * b.y + a.z * b.z;
}

vec3
scale(float s, vec3 a)
{
    vec3 r;
    r.x = s * a.x;
    r.y = s * a.y;
    r.z = s * a.z;
    return r;
}

vec3
add(vec3 a, vec3 b)
{
    vec3 r;
    r.x = a.x + b.x;
    r.y = a.y + b.y;
    r.z = a.z + b.z;
    return r;
}

int
intersect(vec3 a, vec3 b, vec3 *normals, vec3 *points, int nnormals)
{
    vec3 ab = add(b, scale(-1, a));
    float tfirst = 0;
    float tlast = 1;
    int i;
    for(i = 0; i < nnormals; i++)
    {
        float d = dot(normals[i], points[i]);
        float denom = dot(normals[i], ab);
        float dist = d - dot(normals[i], a);
        float t = dist / denom;
        if(denom > 0 && t > tfirst)
        {
            tfirst = t;
        }
        else if(denom < 0 && t < tlast)
        {
            tlast = t;
        }
    }
    return tfirst < tlast ? 1 : 0;
}

const vec3 N = {0,-1,0};
const vec3 S = {0,1,0};
const vec3 W = {-1,0,0};
const vec3 E = {1,0,0};
const vec3 D = {0,0,-1};

int
main(void)
{
    vec3 normals[5];
    vec3 player;
    vec3 *targets;
    int i;
    int j;
    vec3 *buildings;
    vec3 *b;
    int nbuildings = 0;
    int n;
    int m;
    char line[300];
    normals[0] = N;
    normals[1] = S;
    normals[2] = W;
    normals[3] = E;
    normals[4] = D;
    fgets(line, 300, stdin);
    n = atoi(line);
    /*5 sides for each building*/
    buildings = calloc(n * n * 5, sizeof(*buildings));
    b = buildings;
    for(i = 0; i < n; i++)
    {
        char *z;
        fgets(line, 300, stdin);
        for(j = 0; j < n && (z = strtok(j ? NULL : line, " \n")) != NULL; j++)
        {
            vec3 bottom;
            vec3 top;
            if(z[0] == '0') continue;
            nbuildings++;
            bottom.x = j;
            bottom.y = i;
            bottom.z = 0;
            top.x = j + 1;
            top.y = i + 1;
            top.z = atoi(z);
            b[0] = top;
            b[1] = bottom;
            b[2] = top;
            b[3] = bottom;
            b[4] = top;
            b += 5;
        }
    }
    fgets(line, 300, stdin);
    player.x = atof(strtok(line, " "));
    player.y = atof(strtok(NULL, " "));
    player.z = atof(strtok(NULL, " \n"));
    fgets(line, 300, stdin);
    m = atoi(line);
    targets = calloc(m, sizeof(*targets));
    for(i = 0; i < m; i++)
    {
        int hit = 1;
        fgets(line, 300, stdin);
        targets[i].x = atof(strtok(line, " "));
        targets[i].y = atof(strtok(NULL, " "));
        targets[i].z = atof(strtok(NULL, " \n"));
        for(j = 0; j < nbuildings; j++)
        {
            b = &buildings[j * 5];
            if(intersect(player, targets[i], normals, b, 5) == 1)
            {
                hit = 0;
                break;
            }
        }
        printf("%d\n", hit ? 1 : -1);
    }
    free(buildings);
    free(targets);
    return 0;
}

```
> 2 votes

---
Tags: code-golf
---


title: Steampunk: Clacker animation

text:
# Question
Title: Steampunk: Clacker animation
In the highly underrated Steampunk novel *The Difference Engine*, the equivalent of cinema houses delivered a pixelated moving image displayed by tiles which could be flipped mechanically. The control engine for orchestrating the movement of the these tiles was a large noisy machine controlled by a deck of punched cards.

Your task is to emulate such an engine and display a pixelated animation as specified by an input file. The input consists of lines in a fixed-width format, but you may assume whatever is convenient for a line-ending indication. The format is:

```
SSSSYYxxXXOA
SSSS: 4 digit sequence no. may be padded by blanks or all blank
    YY: the y coordinate affected by this line (descending, top is 0, bottom is m-1)
      xx: the starting x coordinate
        XX: the ending x coordinate
          O: hexadecimal opcode
           A: argument (0 or 1)

```

The input is explicitly sequenced (if you ever drop your deck of cards on the floor, you'll thank me for this part). That means the program must perform a stable sort of the input lines using the sequence field as a sort key. Lines with the same sequence number must maintain their original relative ordering. (It should work with an unstable sort, if you append the actual line number to the key.) A blank sequence field should be interpreted as lower than any number (ascii collation sequence).

A single statement line can only affect a single y coordinate, but may specify a contiguous range of x values. The ending x value may be left blank or may be identical to the initial value in order to affect a single pixel.

The opcode is a hexadecimal digit which specifies the Universal Binary Function Code which is used as a rasterop. The argument is 0 or 1. The raster operation performed is

```
pixel = pixel OP argument          infix expression
         --or--
        OP(pixel, argument)        function call expression

```

So the original value of the pixel enters as X in the UBF table, and the argument value from the statement enters as Y. The result of this function is the new value of the pixel. And this operation is performed upon each x,y pair from xx,YY to XX,YY specified in the statement. The range specified by xx and XX includes both end-points. So

```
0000 0 010F1

```

should set pixels 0,1,2,3,4,5,6,7,8,9,10 on row 0.

Output dimensions (*m* x *n*) should be 20 x 20 at a minimum, but may be larger if desired. But the *grain* should show, you know? It's supposed to be *pixelated*. Both graphical and ASCII-art output are acceptable.

If for example, we wanted to make an image of a pixelated figure:

```
  #   #
   ###
   ##
   ####
    #
#### ####
   # #

   ###
   # #
   # #

```

If we draw him with a bit-flipping op, like XOR, it can be drawn and erased regardless of whether the screen is black or white.

```
    00020261
     0 6 661
     1 3 561
     2 3 461
     3 3 661
     4 4 461
     5 0 361
     5 5 861
     6 3 361
     6 5 561
     8 3 561
     9 3 361
     9 5 561
    10 3 361
    10 5 561

```

Duplicating this sequence will make the figure appear and disappear.

A larger animation can be composed out-of-order, by specifying different "shots" in the sequence field.

```
   100 016F0
   101 016F0
   102 016F0
   103 016F0
   104 016F0
   105 016F0
   106 016F0
   107 016F0
   108 016F0
   109 016F0
   110 016F0
   111 016F0
   112 016F0
   113 016F0
   114 016F0
   115 016F0
   200020261
   2 0 6 661
   2 1 3 561
   2 2 3 461
   2 3 3 661
   2 4 4 461
   2 5 0 361
   2 5 5 861
   2 6 3 361
   2 6 5 561
   2 8 3 561
   2 9 3 361
   2 9 5 561
   210 3 361
   210 5 561
    00020261
     0 6 661
     1 3 561
     2 3 461
     3 3 661
     4 4 461
     5 0 361
     5 5 861
     6 3 361
     6 5 561
     8 3 561
     9 3 361
     9 5 561
    10 3 361
    10 5 561
   300020261
   3 0 6 661
   3 1 3 561
   3 2 3 461
   3 3 3 661
   3 4 4 461
   3 5 0 361
   3 5 5 861
   3 6 3 361
   3 6 5 561
   3 8 3 561
   3 9 3 361
   3 9 5 561
   310 3 361
   310 5 561
    00020261
     0 6 661
     1 3 561
     2 3 461
     3 3 661
     4 4 461
     5 0 361
     5 5 861
     6 3 361
     6 5 561
     8 3 561
     9 3 361
     9 5 561
    10 3 361
    10 5 561

```

Producing:

This is so shortest program (by byte-count) wins. Bonus (-50) if the engine makes clickity-clack noises.

# Answer
> 3 votes
## Mathematica, ~~306~~ 281 bytes

This expects the input string to be stored in variable `i`

```
ListAnimate[ArrayPlot/@FoldList[({n,y,x,X,o,a}=#2;MapAt[IntegerDigits[o,2,4][[-1-FromDigits[{#,a},2]]]&,#,{y+1,x+1;;X+1}])&,Array[0&,{20,20}],ToExpression/@MapAt["16^^"<>#&,StringTrim/@SortBy[i~StringSplit~"\n"~StringCases~RegularExpression@"^....|..(?!.?$)|.",{#[[1]]&}],{;;,5}]]]

```

And here with some whitespace:

```
ListAnimate[ArrayPlot /@ FoldList[(
     {n, y, x, X, o, a} = #2;
     MapAt[
      IntegerDigits[o, 2, 4][[-1 - FromDigits[{#, a}, 2]]] &,
      #,
      {y + 1, x + 1 ;; X + 1}
      ]
     ) &,
   Array[0 &, {20, 20}],
   ToExpression /@
    MapAt["16^^" <> # &,
     StringTrim /@
      SortBy[i~StringSplit~"\n"~StringCases~
        RegularExpression@"^....|..(?!.?$)|.", {#[[1]] &}], {;; , 5}]
   ]]

```

This got pretty damn long. This challenge contained a lot of fiddly details, and especially the input parsing takes a lot of code in Mathematica (almost half of it, 137 bytes, are just parsing the input). I ended up switching the language twice before settling on Mathematica (I thought I could save on the input parsing by using Ruby, but then I realised the result needs to be *animated*, so I went back to Mathematica).

# Answer
> 2 votes
## Ungolfed Postscript example

This is a "protocol-prolog"-style program, so the data immediately follows in the same source file. Animated gif files can be produced with ImageMagick's `convert` utility (uses ghostscript): `convert clack.ps clack.gif`.

```
%%BoundingBox: 0 0 321 321

/t { token pop exch pop } def
/min { 2 copy gt { exch } if pop } def
/max { 2 copy lt { exch } if pop } def

/m [ 20 { 20 string }repeat ] def
/draw { change {
        m {} forall 20 20 8 [ .0625 0 0 .0625 0 0 ] {} image showpage
    } if } def

%insertion sort from https://groups.google.com/d/topic/comp.lang.postscript/5nDEslzC-vg/discussion
% array greater_function insertionsort array
/insertionsort
{ 1 1 3 index length 1 sub
    { 2 index 1 index get exch % v, j
        { dup 0 eq {exit} if
            3 index 1 index 1 sub get 2 index 4 index exec
            {3 index 1 index 2 copy 1 sub get put 1 sub}
            {exit} ifelse
        } loop
        exch 3 index 3 1 roll put
    } for
    pop
} def

/process {
    x X min 1 x X max { % change? x
        m y get exch  % row-str x_i
        2 copy get  % r x r_x
        dup         % r x r_x r_x
        0 eq { 0 }{ 1 } ifelse  % r x r_x b(x)
        2 mul a add f exch neg bitshift 1 and   % r x r_x f(x,a)
        0 eq { 0 }{ 255 } ifelse  % r x r_x c(f)
        exch 1 index % r x c(f) r_x c(f)
        ne { /change true def } if
        put
    } for
    draw
} def

{ [ {
     currentfile 15 string
         dup 2 13 getinterval exch 3 1 roll
         readline not{pop pop exit}if
    pop
    [ exch
     /b exch dup 0 1 getinterval exch
     /n exch dup 1 1 getinterval exch
     /seq exch dup 2 4 getinterval exch
     /y exch dup 6 2 getinterval t exch
     /x exch dup 8 2 getinterval t exch
     /X exch dup 10 2 getinterval dup (  ) ne { t exch }{pop 2 index exch} ifelse
     /f exch dup 12 get (16#?) dup 3 4 3 roll put t exch
     /a exch 13 get 48 sub
     /change false def
    >>
}loop ]
dup { /seq get exch /seq get exch gt } insertionsort
true exch
{ begin
    b(A)eq{
        { process } if
    }{
        b(O)eq{
            not { process } if
        }{
            pop
            process
        }ifelse
    }ifelse
    change
    end
} forall
    draw
} exec
   100 016F0
   101 016F0
   102 016F0
   103 016F0
   104 016F0
   105 016F0
   106 016F0
   107 016F0
   108 016F0
   109 016F0
   110 016F0
   111 016F0
   112 016F0
   113 016F0
   114 016F0
   115 016F0
   200020261
   2 0 6 661
   2 1 3 561
   2 2 3 461
   2 3 3 661
   2 4 4 461
   2 5 0 361
   2 5 5 861
   2 6 3 361
   2 6 5 561
   2 8 3 561
   2 9 3 361
   2 9 5 561
   210 3 361
   210 5 561
    00020261
     0 6 661
     1 3 561
     2 3 461
     3 3 661
     4 4 461
     5 0 361
     5 5 861
     6 3 361
     6 5 561
     8 3 561
     9 3 361
     9 5 561
    10 3 361
    10 5 561
   300020261
   3 0 6 661
   3 1 3 561
   3 2 3 461
   3 3 3 661
   3 4 4 461
   3 5 0 361
   3 5 5 861
   3 6 3 361
   3 6 5 561
   3 8 3 561
   3 9 3 361
   3 9 5 561
   310 3 361
   310 5 561
    00020261
     0 6 661
     1 3 561
     2 3 461
     3 3 661
     4 4 461
     5 0 361
     5 5 861
     6 3 361
     6 5 561
     8 3 561
     9 3 361
     9 5 561
    10 3 361
    10 5 561
0000 0 515F1
0000 1 11501
0000 1 115F1

```

---
Tags: code-golf, graphical-output, animation
---


# Question
Title: Convert integer to string preserving order
The quest is to convert an integer to a string in such a way that 1. the order is preserved 2. using the least number of characters in the string.

Let's say I have an integer X; the objective is to create a function `f` (and respective inverse, `g`, such that:

### Conditions

1. `f(X) is a utf-8 string for all integer X`
2. `g(f(X)) = X`
3. Ordering is preserved. That is, if I have another integer Y, X \> Y implies f(X) \> f(Y)
4. The integer means it **can be** negative
5. Assume integers in `[-2^63, 2^63 - 1]`

### Winning criterion

1. The answer must fulfill the conditions above
2. Make `f(X)` represent the number in the least number of UTF-8 characters.
3. Of answers complying with 1 and 2, smallest code wins (sum of code of `f` and code of `g`)

### Example

(Python)

```
def f(x):
    return '%019d' % x  # log10(2^63 - 1) ~ 18.9

def g(x):
    return int(x)

```

Notice that it is not clear that `f` is optimal since it always uses the same number of characters (independent of x).

This is my first challenge here and I'm not sure if this fits this Q&A, but it seemed to me a nice and useful problem. I'm also trying to solve it.

# Answer
> 2 votes
# Perl, 4 per integer, 115 in code

```
sub f{pack W4,map{$_|1<<($x<0?16:17)}unpack n4,pack"q>",$x=pop}sub g{unpack"q>",pack n4,map{$_&65535}unpack W4,pop}

```

**Caveat:** This only works if Perl has 64-bit integers. This is true if `perl -V:ivsize` gives 8.

If `perl -V:byteorder` says 87654321, I believe that you may golf both `"q>"` into `"q"`, for 113 characters, but I have no 64-bit SPARC to test this.

The strings returned by `f` and passed to `g` are **text strings**, not binary strings. A text string is a sequence of Unicode codepoints. A binary string is a sequence of bytes. The order of the strings preserves the order of the integers when one encodes each text string in UTF-8 and checks the lexical order of the UTF-8 bytes.

## Facts about UTF-8

1. Valid codepoints for UTF-8 are from 0 to 0xd7ff, and from 0xe000 to 0x10ffff. See RFC 3629. This makes 1112064 valid codepoints. Surrogates from 0xd800 to 0xdfff are not valid in UTF-8.
2. Strings have the same lexical order in Unicode codepoints and in UTF-8 bytes. It is enough to put the codepoints in order, then the UTF-8 bytes are also in order.

## Scheme of conversion

Because 11120643 \< 264 \< 11120644, there is no scheme that can save every 64-bit integer in 3 or fewer codepoints. Some schemes would use a maximum of 4 codepoints and an average of less than 4. My simple scheme uses 4 codepoints for every integer.

I unpack each 64-bit integer into four unsigned 16-bit integers. To preserve the order of negative integers before positive integers, I put negative integers in plane 1 (Supplementary Multilingual Plane), and non-negative integers in plane 2 (Supplementary Ideographic Plane).

Negative example:

* -9118070288978897167
* 0x81761b61bc5e96f1
* 0x8176 0x1b61 0xbc53 0x96f1
* 0x18176 0x11b61 0x1bc53 0x196f1

Postive example:

* 6359689164524478505
* 0x584227999d61e029
* 0x5842 0x2799 0x9d61 0xe029
* 0x25842 0x22799 0x29d61 0x2e029

## Are 0x1fffe, 0x1ffff, 0x2fffe, 0x2ffff valid in UTF-8?

My scheme uses the Unicode noncharacters 0x1fffe, 0x1ffff, 0x2fffe, 0x2ffff. Perl refuses to encode these in UTF-8.

```
$ perl -MEncode -e 'encode "utf-8", "\x{2fffe}", Encode::FB_CROAK'
"\x{2fffe}" does not map to utf8 at /usr/libdata/perl5/amd64-openbsd/5.16.3/Encode.pm line 160.

```

Unicode Corrigendum #9 clarifies that Unicode noncharacters like 0x2fffe are valid in Unicode strings. There is no requirement to reject them in UTF-8 as Perl is doing. Python, Ruby and Tcl do not reject noncharacters in UTF-8.

The workaround for Perl is to use 'utf8' and not 'utf-8' to encode strings. The 'utf8' encoder skips the checks in the strict 'utf-8' encoder.

## Ungolfed version

```
use strict;
use warnings;

# Convert 64-bit integer to Unicode string.
sub f {
    my $x = shift;

    # Unicode plane = 0x10000 if $x < 0, 0x20000 else
    my $p = 1 << ($x < 0 ? 16 : 17);

    # 1. Pack $x as big-endian signed 64-bit integer "q>".
    # 2. Unpack four big-endian unsigned 16-bit integers "n4".
    # 3. Add Unicode plane.
    # 4. Pack four Unicode characters "W4".
    pack "W4", map({ $_ | $p } unpack("n4", pack("q>", $x)));
}

# Convert Unicode string to 64-bit integer.
sub g {
    # Unpack characters, remove plane, pack and unpack integer.
    unpack "q>", pack("n4", map({ $_ & 65535 } unpack("W4", shift)));
}

# Test program: verify that a lexical sort on UTF-8 octets preserves
# the order of these integers.
use Encode;
my @integers = (-9223372036854775808, -4611686018427387904,
                -9999, -1, 0, 5, 44, 333, 2222, 11111,
                4294967295, 9223372036854775807);
my @strings = map { f $_ } @integers;
@strings = sort { encode('utf8', $a) cmp encode('utf8', $b) } @strings;

my $want = join ',', @integers;
my $have = join ',', map({ g $_ } @strings);
if ($want eq $have) {
    printf "ok\n";
}
else {
    die "not ok: $want ne $have";
}

```

# Answer
> 1 votes
# PowerShell, 185

```
$s=32767
function f($x){$a='';while($x){$r=$x%$s;$a+=[char]($r+$s)
[long]$x=[bigint]::divide($x,$s)};$a}
function g($x){$a=0;0..($x.length-1)|%{$a+=($x[$_]-$s)*[bigint]::pow($s,$_)};$a}

```

## Ungolfed

```
$shift = 32767

function f($number) {
    $string = ''
    while($number) {
        $remain = $number % $shift
        $string += [char]($remain+$shift)
        [long]$number = [bigint]::divide($number, $shift)
    }
    $string
}

function g($string) {
    [long]$number = 0
    0..($string.length-1)|%{$number += ($string[$_]-$shift)*[bigint]::pow($shift, $_)}
    $number
}

```

At most, the output will be length 5.

```
> f ([long]::MaxValue)
耆耟耯耟耇
> g '耆耟耯耟耇'
9223372036854775807
> f ([long]::MinValue)
翷翟翏翟翷
> g '翷翟翏翟翷'
-9223372036854775808

```

---
Tags: string, code-challenge, integer, conversion
---


title: Theatre Seating

text:
# Question
Title: Theatre Seating
# Task

A theatre has 10 rows, labelled `A` to `J` from front to back, and 15 seats in each row, numbered 1 to 15 from left to right.

The program uses the following rules to choose the best seats.

* Rule 1: All seats in one booking must be in the same row, next to each other.
* Rule 2: The seats must be as close to the front as possible, then as close to the left as possible (lowest letter, then lowest number)

Write a function which takes the number of tickets wanted as an integer input (`n`), and outputs the best seats available in a list of length `n`.

Your program should:

* Output `-1` if 1 \> Input or Input \> 15\*
* Output `-1` if the seats aren't available\*
* Have a function `B(n)` that the user can use to input the desired number of seats.

\*You can output the -1 in a list if it makes it easier

# Examples

### I/O

Calling `B(5)` on a new array should return `[A1, A2, A3, A4, A5]`
Calling `B(2)` after that should then return `[A6, A7]`
Calling `B(10)` after that should then return `[B1, B2, ... B9, B10]`
Calling `B(-1)` should always return `-1`

### Un-golfed Solution Python

```
Theatre = [ [False] * 16 ] * 11

def B(n):
    if 0 <= n <= 15:
        for i in range(10):
            for j in range(15-n+1):
                try:
                    if not Theatre[i][j]:
                        if not Theatre[i][j + n]:
                            row = i
                            start = j
                            List = []
                            for q in range(n):
                                List.append(chr(row + 65) + str(start + q + 1))
                                Theatre[row][start + q] = True
                            return List
                except:
                    break
    return -1

```

# Answer
# JavaScript - 172

Function itself is 172:

```
//build persistent seats
m=[];
for(i=10;i--;){m[i]={r:String.fromCharCode(i+65),s:[]};for(j=0;j<15;j++)m[i].s.push(j+1);}

function b(z){for(i=0;i<m.length;i++)for(j=0,u=m[i].s.length;o=[],j<u;j++)if(u>=z&z>0){for(m[i].s=m[i].s.slice(z),p=m[i].s[0]||16;o[--z]=m[i].r+--p,z;);return o;}return-1;}

```

Input:

```
console.log(b(-1));
console.log(b(0));
console.log(b(4));
console.log(b(15));
console.log(b(1));
console.log(b(20));

```

Output:

```
-1
-1
[ 'A1', 'A2', 'A3', 'A4' ]
[ 'B1', 'B2', 'B3', 'B4', 'B5', 'B6', 'B7', 'B8', 'B9', 'B10', 'B11', 'B12', 'B13', 'B14', 'B15' ]
[ 'A5' ]
-1

```
> 4 votes

# Answer
# Javascript (*ES6*) - 130 127 107 101 98

```
B=n=>(a=>{for(;n>0&a<9;)if((b=~~B[++a]+n)<16)for(B[a]=b;n--;)c[n]='ABCDEFGHIJ'[a]+b--})(c=[-1])||c

```

Demo here: http://jsfiddle.net/tBu5G/

Some ideas taken from @edc65
> 4 votes

# Answer
## Haskell, 129

```
t=[[a:show s|s<-[1..15]]|a<-['A'..'J']]
b n=(n%).span((<n).length)
_%(h,[])=([],h)
n%(j,(r:s))=let(t,u)=splitAt n r in(t,j++u:s)

```

Some adjustments had to be made to make this a function in Haskell: `b` returns a pair: the tickets (if possible), and the new state of the theater. `t` is the initial theater state, with all tickets unsold. Also, returning `-1` was unnatural for Haskell, so if no tickets can be issued for a request, the empty list is returned for the tickets.

```
λ: let (k1,t1) = b 5 t
λ: k1
["A1","A2","A3","A4","A5"]

λ: let (k2,t2) = b 2 t1
λ: k2
["A6","A7"]

λ: let (k3,t3) = b 10 t2
λ: k3
["B1","B2","B3","B4","B5","B6","B7","B8","B9","B10"]

λ: let (k4,t4) = b (-1) t3
λ: k4
[]

λ: let (k5,t5) = b 2 t4
λ: k5
["A8","A9"]

```
> 3 votes

# Answer
# Javascript (E6) 99 ~~103 113 121~~

Really you just need to store a number for each row

```
B=n=>{for(r=i=[-1];n>0&i++<9;)if((a=~~B[i]+n)<16)for(B[i]=a;n--;)r[n]='ABCDEFGHIJ'[i]+a--;return r}

```

**Test**

```
'5:'+B(5)+'\n2:'+B(2)+'\n10:'+B(10)+'\n0:'+B(0)+'\n1:'+B(-1))+'\n3:'+B(3)

```

**Ungolfed**

```
B = n => {
  for (r = i = [-1]; n > 0 & i++ < 9;)
    if ((a = ~~B[i] + n) < 16)
      for (B[i] = a; n--; ) r[n] = 'ABCDEFGHIJ'[i] + a--;
  return r;
}

```
> 3 votes

# Answer
# APL (75)

```
T←10 15⍴0⋄B←{(⍵∊⍳15)∧∨/Z←,T⍷⍨⍵/0:+T[P]←{⎕A[⍺],⍕⍵}/¨P←(⊃Z/,⍳⍴T)∘+¨1-⍨⍳1⍵⋄¯1}

```

Test:

```
      B 5
  A1    A2    A3    A4    A5
      B 2
  A6    A7
      B 10
  B1    B2    B3    B4    B5    B6    B7    B8    B9    B10
      B ¯1
¯1
      B 3
  A8    A9    A10

```

Explanation:

* `T←10 15⍴0`: `T` is a 15-by-10 matrix that holds the theater state (0 = free)
* `B←{`...`}`: the function
    + `(⍵∊⍳15)`: if  is a member of the set of integers from 1 to 15,
    + `∨/Z←,T⍷⍨⍵/0`: and `T` contains  zeroes in a row (storing possible start points in `Z`),
    + `:`: then:
        - `(⊃Z/,⍳⍴T)`: select possible start coordinates, and take the first one,
        - `∘+¨1-⍨⍳1⍵`: add `⍵-1` more positions to the right of the start coordinate
        - `P←`: store the coordinates in `P`
        - `{⎕A[⍺],⍕⍵}/¨`: format the coordinates
        - `T[P]←`: store the formatted coordinates at their places in `T`. (any nonzero values in T will do)
        - `+`: return the result, which is the formatted coordinates (the result of an assignment is tacit by default)
    + `⋄¯1`: otherwise, return `¯1`.
> 3 votes

# Answer
# JavaScript (ECMAScript 6 Draft) - ~~96~~ ~~95~~ 91 Characters

A recursive solution:

**Version 1**

```
B=(n,r=0)=>n>0&&(k=~~B[r])+n<16?[...Array(n)].map(_=>'ABCDEFGHIJ'[r]+(B[r]=++k)):r<9?B(n,r+1):-1

```

**Version 2:**

```
B=(n,r=0)=>n<1|r>9?-1:(k=B[r]|0)+n<16?[...Array(n)].map(_=>'ABCDEFGHIJ'[r]+(B[r]=++k)):B(n,r+1)

```

(Thanks to nderscore for the inspiration for the 1 character saving)

**Version 3:**

```
B=(n,r=0)=>n<1|r>9?-1:(B[r]^=0)+n<16?[...Array(n)].map(_=>'ABCDEFGHIJ'[r]+ ++B[r]):B(n,r+1)

```

(Thanks to nderscore)

**Explanation:**

```
B = function(n,r=0)          // Create a function B with arguments:
                             // - n is the number of seats to book
                             // - r is the row number (defaults to 0)
{
  var k = ~~B[r];            // get the number of seats already booked in row r
  if (  n > 0                // ensure that n is a valid booking
     && k+n<16 )             // check that there are enough seats remaining in row r
  {
    var P = new Array(n);    // Create an array with length n with no elements initialised
    var Q = [...P];          // Use P to create an array with every element
                             // initialised to undefined
    var R = 'ABCDEFGHIJ'[r]; // get the row ID.
    B[r] = k + n;            // Increment the number of seats booked in row r by n.
    var S = Q.map(
      function(){
        return R + (++k);    // Map each value of Q to the row ID concatenated with
                             // the seat number.
      }
    );
    return S;                // Return the array of seats.
  }
  else if ( r < 9 )          // If there are more rows to check
  {
    return B(n,r+1);         // Check the next row.
  }
  else                       // Else (if n is invalid or we've run out of rows)
  {
    return -1;               // Return -1.
  }
}

```
> 3 votes

# Answer
# GolfScript, ~~103~~ 82 bytes

```
226,1>15/[0]*:T{:&0>{T[{),&~)>:|T\/,2=}?]{T|-:T;|{(.[15/65+]\15%)`+}%}-1if}-1if}:B

```

# Examples

```
$ cat theatre.gs
226,1>15/[0]*:T
{:&0>{T[{),&~)>:|T\/,2=}?]{T|-:T;|{(.[15/65+]\15%)`+}%}-1if}-1if}:B

5  B p  # Execute B(5), stringify and print.
2  B p
15 B p
17 B p
0  B p

{}:puts # Disable automatic output.
$
$ golfscript theatre.gs
["A1" "A2" "A3" "A4" "A5"]
["A6" "A7"]
["B1" "B2" "B3" "B4" "B5" "B6" "B7" "B8" "B9" "B10" "B11" "B12" "B13" "B14" "B15"]
-1
-1

```

# How it works

```
226,1>           # Push the array [ 1 … 225 ].
15/[0]*          # Split in chunks of 15 elements and join separating by zeros.
:T               # Save result in T.
{                #
  :&0>           # Save the function's argument in & and check if it's positive.
  {              # If it is:
    T[{          # For each seat S in T:
      ),         # Push [ 0 … S ].
      &~)>       # Reduce two [ S-(&-1) … S ].
      :|         # Save the result in |.
      T\/        # Split T around |.
      ,2=        # If there are two chunks, the seats are available.
    }?]          # Find the first S that satisfies the above condition.
    {            # If there was a match:
      T|-:T;     # Remove the seats in | from T.
      |{         # For each seat S in |:
        (.       # Push S+1 S+1.
        [15/65+] # Compute (S+1)/15+65; the ASCII character corresponding to the row.
        \15%)`+  # Compute (S+1)%15+1, stringify and concatenate.
      }%         #
    }            #
    -1if         # If there was no match, push -1 instead.
  }              #
  -1if           # If the argument was non-positive, push -1 instead.
}

```
> 2 votes

# Answer
# CoffeeScript - ~~171~~ ~~150~~ 149

I suspect Ruby or Perl will beat this out before long.

```
c=0;l=64;k=1
f=(n)->
 if n<0 or n>15 or 150-c<n
  return-1
 a=[]
 for i in[1..n]
  if c%15==0
   ++l;k=1
  ++c;a.push String.fromCharCode(l)+k;++k
 a

```

**Equivalent JavaScript/Explanation**:

For those unfamiliar with CoffeeScript.

```
var seats  = 0; //Occupied seats.
var letter = 64; //ASCII code for row letter.
var index  = 1;  //Index of seat in row.

function seats( count )
{
    if( count < 0 || count > 15 || ( 150 - seats ) < count )
        return -1;

    var assignedSeats = [];

    for( var i = 1; i <= count; ++i )
    {
        if( ( seats % 15 ) === 0 )
        {
            ++letter;
            index = 1;
        }

        ++seats; //Occupy a seat.
        assignedSeats.push( String.fromCharCode( letter ) + index );
        ++index;
    }

    return assignedSeats;
}

```

Try it online.
> 1 votes

# Answer
# Cobra - 309

This *should* do it, but I can't actually get to a compiler for a few hours, so I'll update it later if needed.

```
class P
    var s=List<of List<of String>>()
    def main
        for l in 'ABCDEFGHIJ'
            t=[]
            for n in 1:16,t.insert(0,l.toString+n.toString)
            .s.add(t)
    def b(n) as List<of String>
        t=[]
        for r in .s.count,if .s[r].count>=n
            for i in n,t.add(.s[r].pop)
            break
        return if(n>0 and t<>[],t,['-1'])

```
> 0 votes

# Answer
## C# - 289

First attempt at code golfing.

```
int[]s=new int[10];string[]B(int n){string[]x=new string[]{"-1"};if(n<1||n>15)return x;int m=(int)Math.Pow(2, n)-1;for(int i=0;i<10;++i){for(int j=0;j<15-n;++j){if((s[i] &m)==0){s[i]|=m;string[]r=new string[n];for(int k=0;k<n;++k)r[k]=(""+(char)(i+65)+(j+k+1));return r;}m<<=1;}}return x;}

```

Un-golfed

```
int[] s = new int[10];
string[] B(int n)
{
    string[] x = new string[] { "-1" };
    if (n < 1 || n > 15) return x;
    int m = (int)Math.Pow(2, n) - 1;
    for (int i = 0; i < 10; ++i)
    {
        for (int j = 0; j < 15 - n; ++j)
        {
            if ((s[i] & m) == 0)
            {
                s[i] |= m;
                string[] r = new string[n];
                for (int k = 0; k < n; ++k)
                    r[k] = ("" + (char)(i + 65) + (j+k+1));
                return r;
            }
            m <<= 1;
        }
    }
    return x;
}

```
> 0 votes

# Answer
# K, 140

```
d:10#,15#0b
B:{if[(x<0)|x>15;:-1];$[^r:*&&/'~:^a:{(*&&/'{x(!1+(#x)-y)+\:!y}[d x;y])+!y}[;x]'!#d;-1;[.[`d;(r;a r);~:];(10#.Q.A)[r],/:$1+a r]]}

```

There are undoubtedly numerous improvements to be made here
> 0 votes

# Answer
**C++ - 257**

Also a first attempt at golfing.

```
static vector< int > t (10, 0);

vector<string> b(int n){
    vector<string> o;
    int i=0,j;
    for(;i<10&&16>n&&n>0;i++){
        if(15-t[i]<n) continue;
        char l='A'+i;
        for(j=t[i];j<n+t[i];j++){
           o.push_back(l + toS(j + 1));
        }
        t[i]+=n;
        n=0;
    }
    if(o.empty()) o.push_back("-1");
    return o;
}

```

Because to\_string wasn't working with my compiler, toS is defined as

```
string toS(int i){
    return static_cast<ostringstream*>( &(ostringstream() << i) )->str();
}

```

And as a little interface

```
int main(){
int input = 0;
bool done = false;
while (!done){
    cout << "how many seats would you like? (0 to exit)\n";
    cin >> input;
    vector<string> selection = b(input);
    for (auto s : selection){
        cout << s << ' ';
    }
    cout << endl;
    if (input == 0) break;
}
return 0;
}

```
> 0 votes

# Answer
# C# - 268 Bytes

Golfed code:

```
int[]s=new int[10];string[]B(int n){string[]x={"-1"};if(n<1||n>15)return x;int m=(int)Math.Pow(2,n)-1;for(int i=0;++i<10;){for(int j=0;++j<15-n;){if((s[i]&m)==0){s[i]|=m;var r=new string[n];for(int k=0;++k<n;)r[k]=(""+(char)(i+65)+(j+k+1));return r;}m<<=1;}}return x;}

```

Ungolfed code:

```
    int[] s = new int[10];
    string[] B(int n)
    {
        string[] x = { "-1" };
        if (n < 1 || n > 15) return x;
        int m = (int)Math.Pow(2, n) - 1;
        for (int i = 0; ++i < 10;)
        {
            for (int j = 0; ++j < 15 - n;)
            {
                if ((s[i] & m) == 0)
                {
                    s[i] |= m;
                    var r = new string[n];
                    for (int k = 0; ++k < n;)
                        r[k] = ("" + (char)(i + 65) + (j + k + 1));
                    return r;
                }
                m <<= 1;
            }
        }
        return x;
    }

```

I would have written some annotations into a comment on GoldenDragon's solution instead of making my own, but my reputation doesn't allow it.
> 0 votes

---
Tags: code-golf, function
---


title: Create a Question Asker!

text:
# Question
Title: Create a Question Asker!
Writing questions for programming puzzles is tiring and takes many minutes to do. This is where you come in. Your job is to write a program that randomly generates plausible-sounding (but not necessarily interesting) code golf questions.

Input: None

Output: One sentence code golf question (see sentence structure)

Guidelines: **No hardcoding**. The questions don't have to be valid, solvable, or nontrivial. Creativity is encouraged. Voting is based on variety and bonus to programs that can create interesting problems.

Samples:

```
Find the sum of every even number from 1 to 100.
Create a funny sentence without punctuation.
Draw a picture of a cat in 3D.

```

Sentence structure:

```
[verb] [noun goal] [of] [noun specific] [preposition] [noun restriction]

```

# Answer
# NetLogo

```
to go
  type one-of [ "Print" "Calculate" "Find" "Determine" "Output" ]
  type " the "
  type one-of [ "sum" "mean" "average" "median" "standard deviation" "product" "geometric mean"]
  type " of all "
  type one-of [ "prime" "composite" "even" "odd" "perfect" "abundant" "deficient" "square" "triangular" "cubic" "lucky" "friendly" "strictly non-palindromic" ]
  type " numbers from "
  type random 100
  type " to "
  type 100 + random 10000
  type one-of [ " (inclusive)." " (exclusive)." ]
end

```

Sample output (obtained randomly):

```
Find the product of all friendly numbers from 60 to 3112 (inclusive).

```
> 11 votes

# Answer
## C

```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main() {
    srand(time(NULL));
    printf("Find the sum of every even number from 1 to %d.\n", rand());
    return 0;
}

```

On my computer it can generate 2147483648 different challenges.
> 1 votes

# Answer
# Python

```
from random import randint as r
print "Draw a picture of a cat in %iD" % (r(2,4))

```
> 0 votes

---
Tags: popularity-contest, generation, grammars
---


title: Do the needful?

text:
# Question
Title: Do the needful?
**Goal**

Replace all comments in C, C++, or Java Code with the comment `// Do the needful`.

**Specifics**

This coding challenge is a simple one. Take as input the name of a file. The input file shall contain C, C++, or Java code. The code shall contain one or more comments. The comments can be single line `/* */` or `//` delimited, as well as multi-line `/* */` delimited. The output of the program should be identical to the input except all of the comments should be converted to `// Do the needful`.

For example if the input file is:

```
#include <iostream.h>

int   result;    // the result of the calculations
char  oper_char; // the user-specified operator
int   value;     // value specified after the operator

/* standard main function */
int main()
{
    result = 0; // initialize the result

    // Loop forever (or till we hit the break statement)
    while (1) {
        cout << "Result: " << result << '\n';

        /* This code outputs display and requests
           input from the user */
        cout << "Enter operator and number: ";
        cin >> oper_char;
        cin >> value;

        if (oper_char = '+') {
            result += value;
        } else {
            cout << "Unknown operator " << oper_char << '\n';
        }
    }
    return (0);
}

```

The output of the program should read

```
#include <iostream.h>

int   result;    // Do the needful
char  oper_char; // Do the needful
int   value;     // Do the needful

// Do the needful
int main()
{
    result = 0; // Do the needful

    // Do the needful
    while (1) {
        cout << "Result: " << result << '\n';

        // Do the needful
        cout << "Enter operator and number: ";
        cin >> oper_char;
        cin >> value;

        if (oper_char = '+') {
            result += value;
        } else {
            cout << "Unknown operator " << oper_char << '\n';
        }
    }
    return (0);
}

```

**Scoring**

This is a popularity contest. You get two extra votes added to your score if none of the following words appears in your program in any case variation: `{"do", "the", "needful"}`. Score is number of votes plus bonus if applicable.

**Allowances**

If comments appear in string literals it is acceptable to convert them to `// Do the needful` as well. After all... you can never have enough needful.

# Answer
# CoffeeScript (66 bytes)

```
(c)->c.replace /\/\/.*\n?|\/\*[^]*?\*\//g,"// D\o t\he needfu\l\n"

```

This code will parse strings, but there is a good reason. You see, there is a possibility that there is a comment in a template generating C `/**/` comments.

This gets the bonus, as it avoids exact case insensitive matches for `Do`, `the`, and `needful`. It also uses ES5 candle (`[^]`) operator to do stuff. I would put a comment `Do the needful` in this program, but that would remove the bonus.
> 4 votes

# Answer
# Perl, 68 characters

```
perl -0pe's@((//).*?(\n)|(/\*).*?(\*/))@\2\4 Do the needful \3\5@sg'

```

This takes some liberties with the specification, and retains the original comment style. This avoids the problem with `/* ... */` comments appearing before the end of the line.

No attempt is made to avoid comments within string literals, and no claim is made for the bonus points.
> 6 votes

# Answer
# Perl

First world anarchy! :)

"you can never have enough needful"

```
#!perl -p0
sub the { s,(?<=\w)(.*)(\n),$1 // do the needful$2,g }
sub needful { s,//.*\n,\n,g,s,/\*.*?\*/,,msg }

do not do the needful

```
> 5 votes

# Answer
# Python 3.x, regex

Since it's not code golf I didn't fuss about code length. Nothing impressive, but I had fun remembering / relearning regex basics.

```
import re
import urllib.request as r
def dTN(filename):
    dtn = re.search(r"(?<=question-hyperlink\">)([A-Za-z \n]*)(?=[?]<)", r.urlopen("http://codegolf.stackexchange.com/questions/28625/").read().decode("utf8")).group(0)
    with open(filename) as f:
        return re.sub(r"//{1}.*", "//{0}".format(dtn), re.sub(r"/\*[A-Za-z \n]*\*/", "// {0}".format(dtn), f.read()))

```
> 4 votes

# Answer
# sed, 90 characters

Could be improved. I learned a lot about sed while making this.

Reads from standard input, outputs to standard output. Assumes valid input - if you have unterminated comments, it won't treat it as a comment.

Tested on GNU sed v4.2.2.

```
s_/\*.*\*/_//_
tg
s_/\*.*$_//_
tl
:g
s_//.*$_// Do the needful_
P
d
:l
s_.*\*/_//_
tg
N
bl

```

And the prize for readability goes to....?

One-liner version:

```
s_/\*.*\*/_//_;tg;s_/\*.*$_//_;tl;:g;s_//.*$_// Do the needful_;P;d;:l;s_.*\*/_//_;tg;N;bl

```

## Explanation

The control flow jumps around a lot, by means of GOTO statements (yes, sed has them!). sed does not have any loops or convenient conditional statements AFAIK.

```
s_/\*.*\*/_//_              # Substitute /* ... */ with //
tg                          # GOTO g if the substitution occured
s_/\*.*$_//_                # Substitute /*...<ENDOFLINE> with //
tl                          # GOTO l if the substitution occured
:g                          # GOTO-LABEL g
s_//.*$_// Do the needful_  # Replace //...<ENDOFLINE> with // Do the needful
P                           # Print the pattern space (current line with substitutions)
d                           # empty the pattern space and move on to the next line
:l                          # GOTO-LABEL l
s_.*\*/_//_                 # Replace ... */ with //
tg                          # GOTO g if the substitution occured
N                           # take another line from input and add it to the pattern space
bl                          # GOTO l

```
> 2 votes

# Answer
## Rebol

It's not code golf, so I'll be wordy.

```
do-the-needful: function [filename [file!]] [
    parse (data: to-string read filename) [
        ; match the pattern in brackets ANY number of times (zero okay)
        any [
            ; seek the parse position up TO one of the following matches
            ; if a match is hit, following code in parentheses is executed normally
            to [
                "/*" (terminator: "*/")
            |
                "//" (terminator: newline)
            ]

            ; save parse position in start, seek up THRU terminator and leave parse
            ; position at the end of the terminator match (not the beginning as w/TO)
            start:
            thru terminator
            finish:

            ; Do partial replacement within the input; starting at START
            ; but limited to FINISH.  Again, structure in parentheses is exec'd as code
            (
                change/part start combine ["// Do the needful" newline] finish
            )
        ]
    ]
    return data
 ]

```

*(Note: For political reasons, I am pushing COMBINE here, but it's not standard yet. So if you actually want to run this, use REJOIN. But I hate REJOIN. A wart on an otherwise beautiful language! Tell your friendly neighborhood Red dev leads to listen to me. Thanks.)*

PARSE is a dialect, or language-within-a-language, in Rebol and Red. It twists things up, so for instance the symbol types that are used for assignment (the `terminator:` in `terminator: newline`) takes on a new meaning when used in the code-as-data paradigm... it saves the current parse position into a variable with that name. You can read more about why it's cool here.

---

**UPDATE:** Oh all right, I'll golf it too. In Rebmu, 72 chars... using rebmu/args which injects A as the argument:

`pa DtsRDa[anTO["/*"(T"*/")|"//"(Tlf)]SthT F(chpS"// Do the needful^/"f)]d`

Exactly the same program.
> 2 votes

# Answer
## BrainFuck

Yes, BrainFuck is a Turing-complete language.
Good luck for understanding this code.

```
,[.-----------------------------------------------[>+>+<<-]>
>[-<<+>>][-]+<[[-]>-<]>[>,----------------------------------
-------------[>+>+<<-]>>[-<<+>>]<>[-]+<[>-<+++++[>+>+<<-]>>[
-<<+>>]<>[-]+<[>-<++++++++++++++++++++++++++++++++++++++++++
.[-]]>[<+++++++++++++++++++++++++++++++++++++++++++++++.----
-----------.++++++++++++++++++++++++++++++++++++.+++++++++++
++++++++++++++++++++++++++++++++.---------------------------
----------------------------------------------------.+++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++.------------.---.-------------------------
--------------------------------------------.+++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++.---------..-.++.+++++++++++++++.---------.[+++++[,------
------------------------------------],----------------------
-------------------------]>-]<<[-]]>[<++++++++++++++++++++++
+++++++++++++++++++++++++.---------------.++++++++++++++++++
++++++++++++++++++.+++++++++++++++++++++++++++++++++++++++++
++.---------------------------------------------------------
----------------------.+++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++.------------
.---.-------------------------------------------------------
--------------.+++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++.---------..-.++.++++++++++
+++++.---------.[,----------]++++++++++.[-]>-]<<[-]<<>-]<<,]

```

Basically, the pseudo-code is :

```
get input_char
while (input_char is not null)
{
  print input_char
  if (input_char is '/')
  {
    get input_char
    if (input_char is '/')
    {
      print '/ Do the needful'
      get input_char until input_char is '\n'
    }
    else
    {
      if (input_char is '*')
      {
        print '/ Do the needful'
        get input_char until input_char is '*' followed by '/'
      }
      else
      {
        print input_char
      }
    }
  }
  get input_char
}

```

Some online interpreter are broken.
Try it here with the example given by the OP (ended with *null-char* to break the loop properly) :

```
#include <iostream.h>\n\nint   result;    // the result of the calculations \nchar  oper_char; // the user-specified operator \nint   value;     // value specified after the operator\n\n/* standard main function */     \nint main()\n{\n    result = 0; // initialize the result \n\n    // Loop forever (or till we hit the break statement) \n    while (1) {\n        cout << "Result: " << result << '\\n';\n\n        /* This code outputs display and requests\n           input from the user */\n        cout << "Enter operator and number: ";\n        cin >> oper_char;\n        cin >> value;\n\n        if (oper_char = '+') {\n            result += value;\n        } else {\n            cout << "Unknown operator " << oper_char << '\\n';\n        }\n    }\n    return (0);\n}\0

```
> 2 votes

---
Tags: popularity-contest, comment
---


title: Resistors of Unusual Value

text:
# Question
Title: Resistors of Unusual Value
### Introduction

When building an electronics project, a schematic may call for a resistor of an unusual value (say, 510 ohms). You check your parts bin and find that you have no 510-ohm resistors. But you do have many common values above and below this value. By combining resistors in parallel and series, you should be able to approximate the 510-ohm resistor fairly well.

### Task

You must write a function or program which accepts a list of resistor values (resistors you stock) and a target value (which you aim to approximate). The program must consider:

* Individual resistors
* Two resistors in series
* Two resistors in parallel

The program should compute all possible combinations of 1 and 2 resistors from the stock list (including two copies of the same resistor value), compute their series and parallel resistance, then sort the configurations according to how well they approximate the target value.

The output format should be one configuration per line, with a `+` denoting series and `|` denoting parallel, and some space or an = sign before the net resistance.

### Formulas

* The resistance of one resistor is `R1`
* The net resistance of two resistors in series is `R1 + R2`
* The net resistance of two resistors in parallel is `1 / (1/R1 + 1/R2)`
* The distance between an approximated resistance value and the target value can be calculated as pseudo-logarithmic distance, not linear distance: `dist = abs(Rapprox / Rtarget - 1)`. For example, 200 is closer to 350 than it is to 100.
* A better distance measure is true logarithmic distance `dist = abs(log(Rapprox/Rtarget))`, but since this was not specified in the original question, you are free to use either measurement.

### Scoring

Score is measured in characters of code, per usual golf rules. Lowest score wins.

### Example

We have the following resistors in stock `[100, 150, 220, 330, 470, 680, 1000, 1500, 2200, 3300, 4700]` and wish to target `510` ohms. The program should output 143 configurations, approximately as shown (you can change the format, but make sure the meaning is easily determined):

```
680 | 2200     519.444
1000 | 1000    500.
150 + 330      480.
220 + 330      550.
470            470
680 | 1500     467.89
680 | 3300     563.819
100 + 470      570.
220 + 220      440.
100 + 330      430.
470 | 4700     427.273
680 | 4700     594.052
1000 | 1500    600.
470 | 3300     411.406
680 | 1000     404.762
150 + 470      620.
...
many more rows
...
2200 + 4700    6900.
3300 + 4700    8000.
4700 + 4700    9400.

```

In this example, the best approximation of 510 ohms is given by 680- and 2200-ohm resistors in parallel.

**Best of each language so far (1 June 2014):**

1. J - 70 char
2. APL - 102 char
3. Mathematica - 122 char
4. Ruby - 154 char
5. Javascript - 156 char
6. Julia - 163 char
7. Perl - 185 char
8. Python - 270 char

# Answer
# J - 86 71 70 char

```
((]/:[|@<:@%~2{::"1])(;a:,<)"0,[:,/(<,.+`|,.+/;+&.%/)"1@;@((<@,.{:)\))

```

I'm not going to bother to explain every little detail because a lot of the code is spent syncing up the results of different functions, but here's the gist of the golf:

* `;@((<@,.{:)\)` makes every possible pair of resistors, to be connected either in parallel or in series.
* `[:,/(<,.+`|,.+/;+&.%/)"1@` then connects them, in parallel and in series, making a big list of possible connections.
* `(;a:,<)"0,` adds in the possibility of using only one resistor by itself to approximate.
* `(]/:[|@<:@%~2{::"1])` sorts the list of combinations of resistors by the pseudolog distance (`|@<:@%`) between the target and the resultant resistance from each combination.

And this is how to use it:

```
   rouv =: ((]/:[|@<:@%~2{::"1])(;a:,<)"0,[:,/(<,.+`|,.+/;+&.%/)"1@;@((<@,.{:)\))
   # 510 rouv 100 150 220 330 470 680 1000 1500 2200 3300 4700      NB. how many?
143
   10 {. 510 rouv 100 150 220 330 470 680 1000 1500 2200 3300 4700  NB. view first 10
+---------+-+-------+
|680 2200 |||519.444|
+---------+-+-------+
|1000 1000|||500    |
+---------+-+-------+
|150 330  |+|480    |
+---------+-+-------+
|220 330  |+|550    |
+---------+-+-------+
|470      | |470    |
+---------+-+-------+
|680 1500 |||467.89 |
+---------+-+-------+
|680 3300 |||563.819|
+---------+-+-------+
|100 470  |+|570    |
+---------+-+-------+
|220 220  |+|440    |
+---------+-+-------+
|100 330  |+|430    |
+---------+-+-------+

```

You don't have to only view the first 10 like I did above, but this is a function and the J REPL truncates very large return values, and the full output for this example has 287 lines. You can force it all to STDOUT with something like `tmoutput toCRLF , LF ,.~ ": blah rouv blah` on Windows—drop the `toCRLF` on Linux—but `rouv` is a function and internally, all the rows exist.

## Note:

The question seems to have been changed right under our noses, and now the log distance is defined as `abs(log(Rapprox/Rtarget))` instead of `abs(Rapprox/Rtarget-1)`. To correct this in my golf, we can change the `|@<:@%` to `|@^.@%`: `<:` is Decrement while `^.` is Logarithm.
> 6 votes

# Answer
## Mathematica, ~~151~~ 122 characters

Expects the target resistance to be stored in `r` and the list of available resistors in `l`.

```
SortBy[Join[{#,#}&/@l,Join@@(#@@@Union[Sort/@N@l~Tuples~{2}]&/@{{"+",##,#+#2}&,{"|",##,#*#2/(#+#2)}&})],Abs[#[[-1]]/r-1]&]

```

Less golf:

```
SortBy[Join[{#, #} & /@ l,
  Join @@ (# @@@
       Union[Sort /@ N@l~Tuples~{2}] & /@ {{"+", ##, # + #2} &, {"|", ##,
        #*#2/(# + #2)} &})], Abs[#[[-1]]/r - 1] &]

```

The output format differs from the suggested one but configurations are easily determinable. The output is a list of configurations. Each configuration is of one of the following forms:

```
{R1, Total}
{"+", R1, R2, Total}
{"|", R1, R2, Total}

```

So the first three elements of the output read

```
{{"|", 680., 2200., 519.444}, {"|", 1000., 1000., 500.}, {"+", 150., 330., 480.}, ...}

```

If you're fine with rational numbers, I could save two characters from omitting `N@`. That is, the first element (for instance) would be returned as `4675/9` instead of `519.444`.
> 12 votes

# Answer
# APL (102)

```
{V←{⊃¨⍺{⍺,⍺⍺,⍵,'=',⍺⍵⍵⍵}⍺⍺/¨Z/⍨≤/¨Z←,∘.,⍨⍵}⋄K[⍋|¯1+⍺÷⍨0 4↓K←↑('|'{÷+/÷⍺⍵}V⍵),('+'+V⍵),{⍵,'  =',⍵}¨⍵;]}

```

This takes the target resistance as the left argument and a list of available resistors as the right argument.

Explanation:

* `V←{`...`}`: `V` is a function that:
    + `Z/⍨≤/¨Z←,∘.,⍨⍵`: finds every unique combination of two values in ,
        - `Z←,∘.,⍨⍵`: join each value in  with each value in , store in `Z`,
        - `Z/⍨≤/¨Z`: select from `Z` those combinations where the first value is less than or equal to the second value
    + `⍺{`...`}⍺⍺/¨`: and then applies following function, bound with the left function (`⍺⍺`) on the right and the left argument () on the left, to each pair:
        - `⍺,⍺⍺,⍵,'=',⍺⍵⍵⍵`, the left argument, followed by the left bound argument, followed by the right argument, followed by `=`, followed by the right function (`⍵⍵`) applied to both arguments. (This is the formatting function, `X [configuration] Y [equals] (X [fn] Y)`.)
    + `⊃¨`: and then unbox each element.
* `{⍵,' =',⍵}¨⍵`: for each element in , make the configurations for the individual resistors. (, nothing, nothing, `=`, ).
* `('+'+V⍵)`: use the `V` function to make all serial configurations (character is `'+'` and function is `+`).
* `'|'{÷+/÷⍺⍵}V⍵`: use the `V` function to make all parallel configurations (character is `'|'` and function is `{÷+/÷⍺⍵}`, inverse of sum of inverse of arguments).
* `K←↑`: make this into a matrix and store it in `K`.
* `0 4↓K`: drop the 4 first columns from `K`, leaving only the resistance values.
* `|¯1+⍺÷⍨`: calculate the distance between  and each configuration.
* `K[⍋`...`;]`: sort `K` by the distances.
> 10 votes

# Answer
# Python 3 - ~~250~~ ~~247~~ 270 bytes

```
from itertools import*
import sys
r=sys.argv[1:]
t=int(r.pop())
p=set(map(tuple,map(sorted,product(r,r))))
a=[('+'.join(b),sum(map(int,b)))for b in p]+[('|'.join(b),1/sum(map(lambda n:1/int(n),b)))for b in p]
for s in sorted(a,key=lambda b:abs(float(b[1])/t-1)):print(s)

```

Run like this:

```
python resistors.py 100 150 220 330 470 680 1000 1500 2200 3300 4700 510

```

(that is, a space-delimited list of resistors, with the target value at the end)

Output:

```
('2200|680', 519.4444444444445)
('1000|1000', 500.0)
('150+330', 480)
('220+330', 550)
('1500|680', 467.88990825688074)
('3300|680', 563.8190954773869)

[snip]

('2200+4700', 6900)
('3300+4700', 8000)
('4700+4700', 9400)

```

~~I would say that outputting, say, `680|2200` and `2200|680` separately is still pretty clear. If this is unacceptable, I can change it, but it'll cost me bytes.~~ Wasn't acceptable. Cost me bytes. Now I sort the tuples before chucking them into the set, otherwise the solution is identical.
> 4 votes

# Answer
# Ruby 2.1, ~~156~~ 154 bytes

```
s=->(a,z){c={};a.map{|e|a.map{|f|c[e]=e;c[e+f]="#{e}+#{f}";c[1/(1.0/f+1.0/e)]="#{e}|#{f}"}};c.sort_by{|k,|(k/z.to_f-1).abs}.map{|e|puts"#{e[1]}=#{e[0]}"}}

```

## Ungolfed:

```
s =->(a,z) {
  c={}
  a.map{|e|
    a.map{|f|
      c[e]=e
      c[e+f]="#{e}+#{f}"
      c[1/(1.0/f+1.0/e)]="#{e}|#{f}"
    }
  }
  c.sort_by{|k,|
    (k/z.to_f-1).abs
  }.map{|e|
    puts "#{e[1]}=#{e[0]}"
  }
}

```

## What it does:

* For each value `e` in `a`;
    + Iterate through `a`, computing single, series, and parallel values as keys to printed values in hash `c`;
* Determine distance from `z` for each key in `c`; and,
* For each value `e[1]` for each key `e[0]` in `c`, print `e[1]=e[0]`.

## Sample usage:

`s[[100, 150, 220, 330, 470, 680, 1000, 1500, 2200, 3300, 4700], 510]`

## Sample output:

```
2200|680=519.4444444444445
1000|1000=500.0
330+150=480
330+220=550
470=470
1500|680=467.88990825688074
3300|680=563.8190954773869
.
.
.
4700+1500=6200
3300+3300=6600
4700+2200=6900
4700+3300=8000
4700+4700=9400

```
> 3 votes

# Answer
# JavaScript (ECMAScript 6) - 186 Characters

```
f=(R,T)=>(D=x=>Math.abs(x[3]/T-1),r={p:(x,y)=>x*y/(x+y),s:(x,y)=>x+y},[...[[x,0,0,x]for(x of R)],...[[x,y,z,r[z](x,y)]for(x of R)for(y of R)for(z in r)if(x<=y)]].sort((a,b)=>D(a)-D(b)))

```

**Input:**

* An array `R` of resistor strengths; and
* `T`, the target resistance.

**Output:**

An array of arrays (sorted by distance from `T`) each containing:

* the smaller resistor's value;
* the higher resistor's value (or 0 if a solitary resistor);
* `p`, `s` or 0 if the resistors are in parallel, serial or solitary; and
* the net resistance.

**Explanation:**

```
f=(R,T)=>(                               // Create a function f with arguments R & T
  D=x=>Math.abs(x[3]/T-1),               // A function D to calculate relative
                                         // distance from the target value
  r={p:(x,y)=>x*y/(x+y),s:(x,y)=>x+y},   // An object containing the formulae
                                         // to calculate resistance in serial and parallel
  solitary = [[x,0,0,x]for(x of R)],     // Create an array of solitary resistors
  pairs =                                // Use Array Comprehension to create the array of
   [[x,y,z,r[z](x,y)]                    // arrays
      for(x of R)                        // for each resistor value
      for(y of R)                        // for each resistor value (again)
      for(z in r)                        // for both serial & parallel
      if(x<=y)],                         // where the first resistor value is smaller than the second
  [
    ...solitary,                         // Use the spread ... operator to combine
    ...pairs                             // the two arrays
  ]
    .sort((a,b)=>D(a)-D(b))              // Sort the arrays by minimum distance
                                         // and return.
)

```
> 3 votes

# Answer
# Julia - ~~179~~ 163 bytes

```
f(t,s)=(\ =repmat;m=endof(s);A=A[v=(A=s\m).>=(B=sort(A))];B=B[v];F=[s,C=A+B,A.*B./C];n=sum(v);print([[s P=[" "]\m P;A [+]\n B;A [|]\n B] F][sortperm(abs(F-t)),:]))

```

This works the same as the old version, but the argument in the print statement has been organised slightly differently to reduce the number of square brackets necessary. Saves 4 bytes. Absorbing the spaces vector creation into the print argument saves an extra 2 bytes. It has also switched from using "find" to get the relevant indices to using the logical form. Saves 6 bytes. Absorbing the calculation of the index vector into the adjustment of A saved another 2 bytes. Finally, replacing endof(v) with sum(v) saved 2 more bytes. Total saving: 16 bytes.

Old version:

```
f(t,s)=(\ =repmat;m=endof(s);A=s\m;v=find(A.>=(B=sort(A)));A=A[v];B=B[v];F=[s,C=A+B,A.*B./C];n=endof(v);P=[" "]\m;print([[s,A,A] [P,[+]\n,[|]\n] [P,B,B] F][sortperm(abs(F-t)),:]))

```

Within the function, here's what it's doing:

```
\ =repmat            # Overloads \ operator to save lots of characters
m=endof(s)           # Length of input s ("Stock")
A=s\m                # Equivalent to repmat(s,m) (see first command)
B=sort(A)            # Same as A but sorted - rather than cycling through
                     # the resistors m times, it repeats each one m times
v=find(A.>=B)        # Identify which pairs for A,B have A>=B
A=A[v];B=B[v]        # Remove pairs where A<B (prevents duplicates)
F=[s,C=A+B,A.*B./C]  # Constructs vector containing results for single resistor,
                     # resistors in series, and resistors in parallel
n=endof(v)           # equivalent to n=(m+1)m/2, gets number of relevant pairs
P=[" "]\m            # Construct array of blank entries for use in constructing output
print([[s,A,A] [P,[+]\n,[|]\n] [P,B,B] F][sortperm(abs(F-t)),:]))
# The following are the components of the argument in the print statement:
[s,A,A]              # Set of resistor values for resistor 1
[P,[+]\n,[|]\n]      # Operator column, prints either nothing, +, or |
[P,B,B]              # Set of resistor values for resistor 2 (blank for single resistor)
F                    # Contains resulting equivalent resistance
[sortperm(abs(F-t)),:] # Determines permutation for sorting array by distance from Target t
                     # and applies it to array

```

Sample output:

```
julia> f(170,[100,220,300])
300  |  300  150
100  +  100  200
300  |  220  126.92307692307692
220          220
220  |  220  110
100          100
300  |  100  75
220  |  100  68.75
100  |  100  50
300          300
220  +  100  320
300  +  100  400
220  +  220  440
300  +  220  520
300  +  300  600

```
> 3 votes

# Answer
# Javascript (E6) 156 ~~162 164 186~~

**Last Edit** Assuming all resistor values \> 0, you can use them for the loop condition

```
F=(t,s)=>{D=a=>Math.abs(a[1]/t-1);for(i=r=[];a=s[j=i++];r[l]=[a,a])for(;b=s[j--];)l=r.push([a+'+'+b,c=a+b],[a+'|'+b,a*b/c]);return r.sort((a,b)=>D(a)-D(b))}

```

Usage : `F(510, [100, 150, 220, 330, 470, 680, 1000, 1500, 2200, 3300, 4700])`

**Ungolfed**

```
F = (t,s) =>
{
  D = a => Math.abs(a[1]/t-1);
  for (i=r=[]; a=s[j=i++]; r[l]=[a,a])
    for(; b=s[j--];)
      l = r.push([a+'+'+b, c=a+b], [a+'|'+b, a*b/c]);
   return r.sort((a,b) => D(a)-D(b))
}

```
> 2 votes

# Answer
# Javascript, 248 bytes

```
function r(T,L){R=[],O="";for(i in L){R.push([a=L[i],a]);for(j=i;j<L.length;)b=L[j++],s=a+b,R.push([a+"+"+b,s],[a+"|"+b,a*b/s])}R.sort(function(a,b){A=Math.abs;return A(a[1]/T-1)-A(b[1]/T-1)});for(i in R)q=R[i],O+=q[0]+"="+q[1]+"\n";console.log(O)}

```

Usage : `r(510, [100, 150, 220, 330, 470, 680, 1000, 1500, 2200, 3300, 4700]);`

### Output

```
670|2200=519.4444444444445
1000|1000=500
150+330=480

(...such rows...)

2200+4700=6900
3300+4700=8000
4700+4700=9400

```
> 1 votes

# Answer
# Perl, 213 199 185 bytes

**213 bytes:**

```
$t=pop;sub t{abs 1-(split/=/,pop)[1]/$t}sub S{$_[0]+$_[1]}sub P{$_[0]*$_[1]/&S}$"=',';@i=@ARGV;say for sort{t($a)<=>t($b)}grep s!(..\b(\d+)\b,?\b(\d+)?\b\))=\K(??{$2<$3})!$1!ee&&/\d$/,<{S,P}({@i},{@i})= S({@i})=>;

```

**199 bytes:**

```
$t=pop;sub t{abs 1-(split/=/,pop)[1]/$t}sub S{$_[0]+$_[1]}sub P{$_[0]*$_[1]/&S}$"=',';@i=@ARGV;say for sort{t($a)<=>t($b)}grep/(..(\d+),?(\d+)?\))/&&$2>=$3&&($_.=eval$1),<{S,P}({@i},{@i})= S({@i})=>;

```

**185 bytes:**

```
$t=pop;sub t{abs 1-$_[0]=~s!.*=!!r/$t}sub S{$_[0]+$_[1]}sub P{$_[0]*$_[1]/&S}$"=',';$i="{@ARGV}";say for sort{t($a)<=>t$b}grep{my($x,$y)=/\d+/g;$_.='='.eval,$x>=$y}<{S,P}($i,$i) S($i)>

```

Pass all available resistors as arguments. The target resistance should be the last:

```
$ perl -E 'code' R1 R2 R3 ... Rn target

```

### How it works (old code)

* Define subroutines `S` and `P` to compute the sum and parallel values of two resistors.
* Set `$"` to "," to interpolate `@ARGV` inside the `glob` operator
* `<{S,P}({@i},{@i})= S({@i})=>` generates a cartesian of all possibilities:

S(100,100), S(100,150), S(100,220), ... P(100,100), P(100,150) ... S(100), S(150) ...
* Combine `s///ee` with `grep` to evaluate the equivalent resistances and filter out unwanted repeats (performed by `(??{$2<$3})` and `/\d$/`
* `sort` by fitness computed in subroutine `t`

### Changes in new code

* Avoid use of `s///ee`, use shorter regex with conditional checking and `eval` inside `grep`
* Replace repeats of `"{@i}" with`$i\`
* Introduce `$x`, `$y` instead of `$2`, `$3`
* Replace `split/=/,pop` with `$_[0]=~s!!!r`
* No need for trailing `;`
* `eval;` is equivalent to `eval $_;`
* Add `=` along with `eval`-ed answer instead of declaring it up front

### Output:

`P` represents resistors in parallel, `S` represents resistors in series.

```
P(2200,680)=519.444444444444
P(1000,1000)=500
S(330,150)=480
S(330,220)=550
S(470)=470
P(1500,680)=467.889908256881
P(3300,680)=563.819095477387
S(470,100)=570
S(220,220)=440
S(330,100)=430
P(4700,470)=427.272727272727
P(4700,680)=594.052044609665
P(1500,1000)=600
P(3300,470)=411.405835543767
P(1000,680)=404.761904761905
S(470,150)=620
P(2200,470)=387.265917602996
S(220,150)=370
S(330,330)=660
P(1500,470)=357.868020304569
S(680)=680
P(680,680)=340
P(2200,1000)=687.5
S(330)=330
S(470,220)=690
S(220,100)=320
P(1000,470)=319.727891156463
P(4700,330)=308.349900596421
S(150,150)=300
P(3300,330)=300
P(2200,330)=286.95652173913
P(680,470)=277.913043478261
P(1500,330)=270.491803278689
P(1500,1500)=750
P(3300,1000)=767.441860465116
S(150,100)=250
P(1000,330)=248.12030075188
S(680,100)=780
P(470,470)=235
P(680,330)=222.178217821782
S(470,330)=800
S(220)=220
P(4700,220)=210.162601626016
P(3300,220)=206.25
S(100,100)=200
P(2200,220)=200
P(4700,1000)=824.561403508772
P(470,330)=193.875
P(1500,220)=191.860465116279
S(680,150)=830
P(1000,220)=180.327868852459
P(680,220)=166.222222222222
P(330,330)=165
S(150)=150
P(470,220)=149.855072463768
P(4700,150)=145.360824742268
P(3300,150)=143.478260869565
P(2200,150)=140.425531914894
P(1500,150)=136.363636363636
P(330,220)=132
P(1000,150)=130.434782608696
P(2200,1500)=891.891891891892
P(680,150)=122.89156626506
S(680,220)=900
P(470,150)=113.709677419355
P(220,220)=110
P(330,150)=103.125
S(100)=100
P(4700,100)=97.9166666666667
P(3300,100)=97.0588235294118
P(2200,100)=95.6521739130435
P(1500,100)=93.75
P(1000,100)=90.9090909090909
P(220,150)=89.1891891891892
P(680,100)=87.1794871794872
P(470,100)=82.4561403508772
S(470,470)=940
P(330,100)=76.7441860465116
P(150,150)=75
P(220,100)=68.75
P(150,100)=60
P(100,100)=50
S(1000)=1000
S(680,330)=1010
P(3300,1500)=1031.25
S(1000,100)=1100
P(2200,2200)=1100
P(4700,1500)=1137.09677419355
S(680,470)=1150
S(1000,150)=1150
S(1000,220)=1220
P(3300,2200)=1320
S(1000,330)=1330
S(680,680)=1360
S(1000,470)=1470
P(4700,2200)=1498.55072463768
S(1500)=1500
S(1500,100)=1600
S(1500,150)=1650
P(3300,3300)=1650
S(1000,680)=1680
S(1500,220)=1720
S(1500,330)=1830
P(4700,3300)=1938.75
S(1500,470)=1970
S(1000,1000)=2000
S(1500,680)=2180
S(2200)=2200
S(2200,100)=2300
S(2200,150)=2350
P(4700,4700)=2350
S(2200,220)=2420
S(1500,1000)=2500
S(2200,330)=2530
S(2200,470)=2670
S(2200,680)=2880
S(1500,1500)=3000
S(2200,1000)=3200
S(3300)=3300
S(3300,100)=3400
S(3300,150)=3450
S(3300,220)=3520
S(3300,330)=3630
S(2200,1500)=3700
S(3300,470)=3770
S(3300,680)=3980
S(3300,1000)=4300
S(2200,2200)=4400
S(4700)=4700
S(3300,1500)=4800
S(4700,100)=4800
S(4700,150)=4850
S(4700,220)=4920
S(4700,330)=5030
S(4700,470)=5170
S(4700,680)=5380
S(3300,2200)=5500
S(4700,1000)=5700
S(4700,1500)=6200
S(3300,3300)=6600
S(4700,2200)=6900
S(4700,3300)=8000
S(4700,4700)=9400

```
> 0 votes

---
Tags: code-golf, electrical-engineering
---