title: Pokeball Simulator

text:
# Question
Title: Pokeball Simulator
In the Pokemon video games, the player is sent out into the world to force wild animals into tiny balls and train them to fight. Of course, *everyone* knows that *no one* plays Pokemon for the battling. The real draw the series has is the pokemon catching itself! Your job is to simulate the pokeball during a capture attempt. This challenge will use the generation V capture formula, which is as follows:

`HP_max` is equal to the target pokemon's maximum HP. `HP_current` is equal to the target pokemon's current HP. `rate` is the catch rate of the pokemon, `bonus_ball` is the thrown pokeball's multiplier, and `bonus_status` is 2.5 if the target pokemon is asleep or frozen, 1.5 if the target pokemon is paralyzed, poisoned, or burned, and 1 otherwise.

After finding `a`, you are to perform up to three "shake checks". The probability of a shake check succeeding is `65536 / (255 / a)^(1/4)`. If any one of these checks fails, the pokemon escapes its ball. If all three checks are successful, the pokemon is caught!

Note: Whenever any division is performed, the result is rounded down to a multiple of 1/4096. This is generally an insignificant detail, but it must be accounted for in your program.

Your challenge is to write a program that executes the shake checks and prints to stdout the status of the checks. On stdin, your program will receive (at least, details below) the maximum HP of the pokemon, the catch rate of the target pokemon, and the name of the pokeball. The maximum HP and the catch rate are both guaranteed to be integers, while the name of the pokeball is always a string. This input may come in any order and with any delimiting character(s) is convenient for you, so long as it's consistent. Assume that the input is correct, no error handling is required.

The names of the pokeballs you are required to support and their catch multipliers are listed here:

```
  Poke | 1
 Great | 1.5
 Ultra | 2
Master | 255

```

You may assume that the target is asleep and at 1 HP. The expected format for output is this:

```
(First check failed)
(no output)

(Second check failed)
*shake*

(Third check failed)
*shake*
*shake*
*shake*

(All checks pass)
*shake*
*shake*
*shake*
Click!

```

(That isn't a typo, your program should never output just two shakes.)

This is , so your score is your program's source code's byte count. Lowest score wins.

# Bonuses!

I said that you *may* assume the pokemon is at 1 HP and asleep. Alternatively, you may allow the user to input the pokemon's current HP and `bonus_status`. The pokemon's current HP will always be an integer equal to or less than its maximum HP, and `bonus_status` will always be either 2.5, 1.5 or 1. If you do, you must have these values at the end of your input, and default to 1 and 2.5 if they're not supplied. You may subtract **15** points from your score for implementing one of these, or **25** for both.

Additionally, you may implement critical captures. If a critical capture occurs, only one shake test is performed. If failed, the program exits silently. If passed, it outputs:

```
*shake*
Click!

```

Critical captures become more common as the player collects more pokemon, but for simplicity's sake we can assume that they have already "caught 'em all". If a randomly generated number between 0 and 2047 is less than `a` (the result of the first calculation) multiplied by 2.5, that's a critical capture. Support for critical captures allows you to remove **25** points from your score.

There are a number of other pokeballs you may choose to support. Their names and catch multipliers are listed here:

```
Safari | 1.5
 Sport | 1.5
  Lure | 3
   Net | 3
  Dusk | 3.5
  Dive | 3.5
  Moon | 4
  Fast | 4
 Quick | 5
  Love | 8

```

For each of these balls you add support for, you may subtract **(5 + the length of the ball's name)** from your score.

Finally, for kicks, achieving all of these bonuses (current HP and bonus\_status from stdin, critical captures, and all 10 optional balls) will net you an additional reward of **7** points removed from your score, for an even **150** total bonus.

# Example Input/Output

Just to ensure we're all on the same page.

```
$ ./balls <<< "19,Ultra,255"
*shake*
*shake*
*shake*
Click!

```

Good luck, and happy golfing!

# Answer
## J 301-150 = 151

For sports, all bonuses implemented, though I'd probably be better off not to :). I shortly explained things below, but this one is far too long to explain in detail, unless someone explicitly requests. It implements all balls, critical captures, and optional inputs.

```
tm =: =*./@:+.' '=] NB. Template match, match non-blanks in right with left
balls  =: 'MMLLPGSUNDFQ',.12{.'oauo' NB. space = wildcard.
NB. lookup function: name -> bonus_ball
lookup =: 4 255 3 8 1 1.5 1.5 2 3 3.5 4 5 #~ (tm"1&balls)@(2&{.)

NB. convert given option
options =: ;".`lookup@.(_=_&".);._2 ,&',' i3 NB. parse options to numeric values
NB. add defaults if necessary
complete =: (, 1 2.5{.~(5-$)) options
NB. formula
r=: <.&.(*&4096)                              NB. round to 1/4096
NB. a=: ((3*zeroth - 2*thirth)*first*second*fourth)/(3*zeroth)
a=:r(1-3%~2*%/3 0{complete)**/1 2 4{complete  NB. A prime, already divided by 255

NB. Critical captures
crit =: >2r5*[:?11^~2: NB. check for critical, k a
mess =: 2 7$'*shake*Click! '"_ NB. Message template
check =: >"0 [:?(4$2^16)"_     NB. Perform 4 checks
mes2 =: mess#~3(<.,<)]          NB. Construct message from number of passed checks
NB. If critical, just output the message array, else do the 4 tests, and execute mes2 on their running and (meaning count the number of uninterrupted trues)
echo mes2@(+/)@(*./\)@(check"0)@(65536%4%:[:r 255%])`mess@.crit a

```

Here the golfed version

```
NB. Golfed verion
echo(m#~3(<.,<)])@(+/)@(*./\)@(>"0[:?(4$2^16)"_)@(65536%4%:[:r 255%])`(m=:2 7$'*shake*Click! '"_)@.(>2r5*[:?11^~2:)(r=:<.&.(*&4096))(1-3%~2*%/3 0{co)**/1 2 4{co=:(,1 2.5{.~(5-$));(".`(4 255 3 8 1 1.5 1.5 2 3 3.5 4 5 #~((=*./@:+.' '=])"1)&('MMLLPGSUNDFQ',.12{.'oauo')@(2&{.)))@.(_=_&".);._2,&','stdin''

```
> 3 votes

# Answer
# PYTHON 249 bytes - 75 for bonuses = 174

My first try ever golfing.

```
import sys,random
y=sys.argv
d,b,f={10:1,1:1.5,15:2,7:1.5,13:255,-2:3.5,6:3,8:3,0:4,11:5},3*int(y[1]),"*shake*\n"
s=lambda:random.random()*(255*b)**.25<65536*((b-2)*int(y[3])*d[ord(y[2][0])-70]*2.5)**.25
if s():print f*3+"Click!" if s()and s()else f

```

Bonus for including selected balls: Safari, Sport, Lure, Net, Dusk, Dive, Fast, Quick

Giving me 8\*5+6+5+4+3+4+4+4+5=75 bonus points

\[edit\] Round down to 12 fractional bits every time division is used by not using it

\[edit2\] optimize pokeball dictionary
> 6 votes

# Answer
# Perl 1 (374 - 150 = 224 + MissingNo. bytes)

```
sub h{print "*shake*
";}($x,$h,$_,$c,$s)=split(/,/,<>);$G=$$%(/P/?256:/U/?151:201);$S=$G-($s==1?0:$s==1.5?12:25);
$F=255&int(int($h*255/(/G|S/?8:12))/(int($x/4)||1));sub c{for($i=0;$i<3;$i++){do h();}print "Click!
";exit;}
/M/||$S<0||$S<$c&&$F>$$*$$%255&&do c();$W=int(int($c*100/(/P/?255:/U/?150:200))*$F/255)+($s==1?0:$s==1.5?5:10);$W>9&&do h();$W>29&&do h();$W>69&&do h();

```

Argument list:

```
current hp, max hp, pokéball, catch rate, status, critical capture

```

Yes, I'm aware this completely breaks the rules, but I don't care. In case you haven't noticed, this is first Pokémon generation capture algorithm, with all its quirks (Great Balls are better than Ultra Balls, in certain conditions). This implements all features, including ones that aren't included (and I decided to include points for them anyway). Critical captures are ignored (but they are implemented - just that they don't affect the capture rate), newer Poké Balls load data of other Poké Balls.

Please note that while this answer is short, it breaks all the rules, so consider it just to be a fun answer, don't accept it. I was initially going to implement Gen5 algorithm in Perl 5, but I decided - why not have some fun. And yes, I actually compiled Perl 1, and this code works. If you run it in newer version of Perl, you may get warnings about deprecated use of `do`, but let's be honest - it's the only way to run functions in Perl 1. Perl 1 also has some quirks on its own (for example, I cannot move the line starting with `/M/` to previous line - why? - I don't know).

Also, there are no random numbers in Perl 1, so hope you won't kill me for modulo of `$$`. It's the closest thing to the random number I could have found.

Edit: It appears that the old `do call()` syntax was removed in Perl 5.19.8. Make sure you use an older version of Perl to run this script, as it appears that Perl 5.20 won't be compatible with Perl 1 scripts.
> 6 votes

# Answer
# PHP (~~746~~ 763 bytes - all bonuses):

```
<?if(!$i=fgets(STDIN))die('');parse_str($i,$i);$b=array('poke'=>1,'great'=>1.5,'ultra'=>2,'master'=>255,'safari'=>1.5,'sport'=>1.5,'lure'=>3,'net'=>3,'dusk'=>3.5,'dive'=>3.5,'moon'=>4,'fast'=>4,'quick'=>5,'love'=>8);$s=array('sleep'=>2.5,'frozen'=>2.5,'paralyzed'=>1.5,'poisoned'=>1.5,'burnt'=>1.5,''=>1);$i=array_merge(array('ball'=>'poke','hp'=>array('max'=>25,'current'=>1),'status'=>2.5,'rate'=>255),$i);$l='strtolower';$r='mt_rand';$x='*shake*'.PHP_EOL;$c='Click!'.PHP_EOL;$a=(((3*$i[hp][max])-(2*$i[hp][current]))*$i[rate]*$b[$l($i[ball])])/(3*$i[hp][max])*(is_numeric($i[status])?$i[status]:$s[$l($i[status])]);$a=((pow(65536/(255/$a),0.25)*4096)<<0)/4096;if($r(0,1)>$a)die();echo$x;if($a>1)die($c);if($r(0,1)>$a)die();echo$x,$x;if($r(0,1)>$a)die();echo$c;

```

To use this, you have to provide the input as 'ball=poke&status=sleep' on STDIN.

The HP must be provided as 'hp\[max\]' or 'hp\[current\]'.

This code works, as tested here.

You can provide the status by it's name or the multiplier. (**not required in the question**).

Here is a readable version:

```
if(!$info=fgets(STDIN))die('');
parse_str($info,$info);
$balls=array(//list of pokeballs
    'poke'=>1,
    'great'=>1.5,
    'ultra'=>2,
    'master'=>255,
    'safari'=>1.5,
    'sport'=>1.5,
    'lure'=>3,
    'net'=>3,
    'dusk'=>3.5,
    'dive'=>3.5,
    'moon'=>4,
    'fast'=>4,
    'quick'=>5,
    'love'=>8
);
$status=array(//list of status
    'sleep'=>2.5,
    'frozen'=>2.5,
    'paralyzed'=>1.5,
    'poisoned'=>1.5,
    'burnt'=>1.5,
    ''=>1 //in case there is no status
);
$info=array_merge(//this will set the default values
    array(
        'ball'=>'poke',
        'hp'=>array('max'=>25,'current'=>1),
        'status'=>2.5,
        'rate'=>255
    ),
    $info
);
$a=(((3*$info['hp']['max'])-(2*$info['hp']['current']))*$info['rate']*$balls[strtolower($info['ball'])])/(3*$info['hp']['max'])*(is_numeric($info['status'])?$info['status']:$status[strtolower($info['status'])]);
$a=((pow(65536/(255/$a),0.25)*4096)<<0)/4096;//same as $a=floor(pow(65536/(255/$a),0.25)*4096)/4096;

if(mt_rand(0,1)>$a) die();//test 1
echo '*shake*',PHP_EOL;
if($a>1)die('Click!'.PHP_EOL);//if $a>1, catch it (critical catch)

if(mt_rand(0,1)>$a) die();//test 2
echo'*shake*',PHP_EOL,'*shake*',PHP_EOL;

if(mt_rand(0,1)>$a) die();//test 3
echo 'Click!',PHP_EOL;//passed all tests

```

I had to edit this because i was using a much higher precision than the required.

The fix was provided by TheConstructor.
> 5 votes

# Answer
# Java, 611

```
import java.util.*;class P{enum B{DI(35),DU(35),FA(40),GR(15),LO(80),LU(30),MA(2550),MO(40),NE(30),PO(10),QU(50),SA(15),SP(15),UL(20);long v;B(int i){v=((long)i<<12)/(long)10;}}public static void main(String[]y){Scanner s=new Scanner(System.in);B b=B.valueOf(s.next().toUpperCase().substring(0,2));long c=(long)(s.nextDouble()*4096);long m=s.nextLong()<<12;long h=(s.hasNextInt()?s.nextLong():1)<<12;long S=(long)((s.hasNextDouble()?s.nextDouble():2.5)*4096);long p=(65536L<<12)/(long)(Math.sqrt(Math.sqrt((255L<<24)/((((3L*m-2L*h)*c>>12)*b.v>>12<<12)/(3L*m)*S>>12)))*512);Random r=new Random();System.out.print(r.nextInt(65536)<p?"*shake*\n"+(r.nextInt(65536)<p?"*shake*\n*shake*\n"+(r.nextInt(65536)<p?"Click!\n":""):""):"");}}

```

Score:

* 729 Bytes
* -93 all Balls
* -25 optional current\_hp and bonus\_state

=\> 611

The program uses fixed-point-arithmetics with 12 fraction-bits (`1/4096` is the value of the right most bit). As Java does not usually use fixed-point there are quite some shifts inside the code to achieve the expected results. See long version for the used arithmetic functions, which have been inlined for golfing purposes.

While most calculations could have been done on `int` values, divisions work better with `long`s as you need to shift the dividend by another 12 bit to the left to keep the desired precision (otherwise you loose all fraction-bits).

Sample input ( `;` is only required if run interactively i.e. STDIN has not received EOF): Ball, catch\_rate, max\_hp

> ```
> Poke 15 255 ;
>
> ```

Sample output:

> ```
> *shake*
>
> ```

Sample input: Ball, catch\_rate, max\_hp, current\_hp, bonus\_state

> ```
> Moon 42 255 50 1.5
>
> ```

Sample output:

> ```
> *shake*
> *shake*
> *shake*
> Click!
>
> ```

```
import java.math.BigDecimal;
import java.util.Random;
import java.util.Scanner;

class Pokeball {
    static long shift(long i) {
        return i << 12;
    }
    enum B {
        DI(35),DU(35),FA(40),GR(15),LO(80),LU(30),MA(2550),MO(40),NE(30),PO(10),QU(50),SA(15),SP(15),UL(20);
        long v;
        B(int i) {
            v = semiFixedDivision(shift(i),10);
        }
    }

    public static void main(String[] args) {
        final Scanner s = new Scanner(System.in);
        B b = B.valueOf(s.next().toUpperCase().substring(0, 2));
        long catchRate = (long) (s.nextDouble() * 4096);
        long maxHp = shift(s.nextLong());
        long currentHp = shift(s.hasNextInt()?s.nextInt():1);
        long statusBonus = (long) ((s.hasNextDouble()?s.nextDouble():2.5) * 4096);
        long a = fixedMultiplication(fixedDivision(fixedMultiplication(fixedMultiplication(
                semiFixedMultiplication(3, maxHp) - semiFixedMultiplication(2, currentHp), catchRate), b.v),
                                                   semiFixedMultiplication(3, maxHp)), statusBonus);
        println("a=",a);
        long x = fixedFourthRoot(fixedDivision(shift(255), a));
        println("x=",x);
        println("x^4=",fixedMultiplication(fixedMultiplication(x,x), fixedMultiplication(x,x)));
        long p = semiFixedDivision(shift(65536), fixedFourthRoot(fixedDivision(shift(255), a)));
        Random r = new Random();
        System.out.print(r.nextInt(65536) < p ?
                         "*shake*\n" + (r.nextInt(65536) < p ?
                                        "*shake*\n*shake*\n" + (r.nextInt(65536) < p ?
                                                                "Click!\n" :
                                                                "") :
                                        "") :
                         "");
    }

    private static long unshift(long p) {
        return p >> 12;
    }

    private static void println(String s, long v) {
        System.out.print(s);
        println(v);
    }

    private static void println(long v) {
        System.out.printf("%s%n", BigDecimal.valueOf(v).divide(BigDecimal.valueOf(4096)));
    }

    /**
     * Calculates division of {@code a/b} with both number last 12 bits treated as being "right of the dot"
     */
    static long fixedDivision(long a, long b) {
        return (a<<12)/b;
    }

    /**
     * Calculates division of {@code a/b} with {@code a}'s last 12 bits treated as being "right of the dot"
     */
    static long semiFixedDivision(long a, long b) {
        return a/b;
    }
    static long fixedMultiplication(long a, long b) {
        return (a*b) >> 12;
    }
    static long semiFixedMultiplication(long a, long b) {
        return a*b;
    }
    static long fixedFourthRoot(long a) {
        return (long)(Math.sqrt(Math.sqrt(a)) * 512);
    }
}

```
> 3 votes

# Answer
# CoffeeScript - ~~317~~ ~~313~~ ~~310~~ ~~307~~ ~~306~~ ~~294~~ ~~270~~ ~~250~~ 242 bytes

**342 - 25** (parameters) **\- 75** (12 balls) **= 242**

```
_=process.stdin
l=console.log
m=Math
s=m.sqrt
t=['*shake*','Click!']
n=65536
_.resume()
_.setEncoding 'utf8'
_.on 'data',(d)=>
 [A,B,C,E,F]=d.match /\w+/g;E||=1;F||=2.5;i=0;while i++<3
  if n*(s s (3*A-2*E)*B*{P:1,G:1.5,U:2,M:255,S:1.5,L:3,N:3,D:3.5,F:4,Q:5}[C.charAt 0]*F)<m.floor(m.random()*n)*s s 765*A
   break
  l t[0]
 if i>2
  l t[i-3]

```

Expects input `HP_max,Rate,Ball[,HP_current[,status]]`. Does not support `Moon` or `Love` balls.

This is the first thing I ever golfed that's not a regex, so there is probably room for improvement. I've shamelessly copied the idea to store only partial ball names. ;) Supporting the other two balls is simply not worth it, not even with the additional **+7** for getting all bonuses.

## Ungolfed version

This version omits all the short aliases I define at the beginning, but does define the ball-lookup separately.

```
balls =
  P: 1
  G: 1.5
  U: 2
  M: 255
  S: 1.5
  L: 3
  N: 3
  D: 3.5
  F: 4
  Q: 5

messages = ['*shake*', 'Click!']

process.stdin.resume()
process.stdin.setEncoding 'utf8'
process.stdin.on 'data', (data) =>
  [HP_max, rate, ball, HP_current, status] = data.match /\w+/g
  HP_current ||= 1
  HP_status ||= 2.5
  i = 0
  while i++ < 3
    if 65536 * (Math.sqrt Math.sqrt (3*HP_max - 2*HP_current)*rate*status*balls[ball.charAt 0]) < Math.floor(Math.random()*65536) * Math.sqrt Math.sqrt 765*HP_max
      break
    console.log messages[0]
  if i > 2
    console.log messages[i-3]

```

A note on the probability formula: I've rearranged the full formula (with written out `a`) so that there are no divisions, and I'm computing `(...)^(1/4)` by taking the square root twice.
> 1 votes

# Answer
Update: (C#)

Byte count: 3,600

Critcal: -25

All poke-balls: -91

---

Total = 3,484

\[golfed\]

```
using System;using System.Text;using System.Security.Cryptography;using System.Linq;namespace Pokemon{public class MainClass{private string[] c(string[] i){if(i.Length <= 3){var v1 =i[0][0];var v2 =i[1][0];var v3 =i[2][0];if(v1>='0'&&v1<='9'&&v2>='a'&&v2<='z'&&v3>='0'&&v3<='9')return new string[]{i[0],i[2],i[1]};else if(v1>='0'&&v1<='9'&&v2>='0'&&v2<='9'&&v3>='a'&&v3<='z')return new string[]{i[0],i[1],i[2]};else if(v1>='a'&&v1<='z'&&v2>='0'&&v2<='9'&&v3>='0'&&v3<='9')return new string[]{i[1],i[2],i[0]};else return null;}else return null;}private static void Main(string[] args){while(true){Console.Clear();MainClass _c = new MainClass();Console.Write("Inputs'please:");var i = Console.ReadLine().ToLower();string[] r = _c.c((string[])(i.Split(new Char[]{' ','.',',','\n','\t','!','@','#','$','%','^','&','&','*','(',')','-','_','+','=','?','/','\\'},StringSplitOptions.RemoveEmptyEntries).Select(p=>p.Trim()).ToList()).ToArray());new w("Processing...\n");if(r== null)new w("Too many errors");else new m(r);}}}public class w{public w(string l){Console.WriteLine(l);}}public class m{public m(string[] v){switch (v[2].Substring(0,2)){case "po":c(v[0],v[1],"1");break;case "ul":c(v[0],v[1],"2");break;case "ma":c(v[0],v[1],"255");break;case "gr":case "sa":case "sp":c(v[0],v[1],"1.5");break;case "lu":case "ne":c(v[0],v[1],"3");break;case "du":case "di":c(v[0],v[1],"3.5");break;case "mo":case "fa":c(v[0],v[1],"4");break;case "qu":c(v[0],v[1],"5");break;case "lo":c(v[0],v[1],"8");break;default:new w("Not supported");break;}}private double y(double v){return Convert.ToDouble(((double)1/(double)4096)*(v/Convert.ToDouble(1/4096)-(v%Convert.ToDouble(1/4096))));}private bool i(double v,double r,double b){if(((double)new Random().Next(0,(int)r))>b*v)return true;else return false;}private double f(double r, double h, double b){return 2.5*y((((3.0*h)-2.0)*r*b)/(3.0*h));}private void c(params string[] v){var s =0.0;var x =0;if(int.Parse(v[1])>100&&int.Parse(v[1])<= 255){s =f(double.Parse(v[0]),double.Parse(v[1]),double.Parse(v[2]));x=0;}else if(int.Parse(v[0])>100&&int.Parse(v[0])<= 255){s =f(double.Parse(v[1]),double.Parse(v[0]),double.Parse(v[2]));x=1;}else{new w(String.Format("Which number is the Max HP? :{0} or {1}:",v[0],v[1]));var c_ = int.Parse(Console.ReadLine());s =f((double.Parse(v[0])+double.Parse(v[1]))-double.Parse(v[c_]),double.Parse(v[c_]),double.Parse(v[2]));x=2;}if(((double)new Random().Next(0, 2047))<s*2.5)new w("*shake*\nClick!");else{for(int c_= 0;c_<3;c_++){new w("*shake*");var r =Math.Pow(65536.0/y(255.0/s),0.25);if(i(r,double.Parse(v[x]),2.5)==true){new w("Click!");break;}else;}}Console.ReadKey();}}}

```

\[regular\]

```
using System;
using System.Text;
using System.Security.Cryptography;
using System.Linq;

namespace Pokemon
{
    public class MainClass
    {
        private string[] c(string[] i)
        {
            if (i.Length <= 3)
            {
                var v1 =i[0][0];
                var v2 =i[1][0];
                var v3 =i[2][0];
                if(v1>='0'&&v1<='9'&&v2>='a'&&v2<='z'&&v3>='0'&&v3<='9')return new string[]{i[0],i[2],i[1]};
                else if(v1>='0'&&v1<='9'&&v2>='0'&&v2<='9'&&v3>='a'&&v3<='z')return new string[]{i[0],i[1],i[2]};
                else if(v1>='a'&&v1<='z'&&v2>='0'&&v2<='9'&&v3>='0'&&v3<='9')return new string[]{i[1],i[2],i[0]};
                else return null;
            }
            else return null;
        }

        private static void Main(string[] args)
        {
            while(true)
            {
                Console.Clear();
                MainClass _c = new MainClass();
                Console.Write("Inputs'please:");
                var i = Console.ReadLine().ToLower();
                string[] r = _c.c((string[])(i.Split(new Char[]{' ','.',',','\n','\t','!','@','#','$','%','^','&','&','*','(',')','-','_','+','=','?','/','\\'},StringSplitOptions.RemoveEmptyEntries).Select(p=>p.Trim()).ToList()).ToArray());
                new w("Processing...\n");
                if(r== null)new w("Too many errors");
                else new m(r);
            }
        }
    }

    public class w
    {
        public w(string l)
        {
            Console.WriteLine(l);
        }
    }

    public class m
    {
        public m(string[] v)
        {
            switch (v[2].Substring(0,2))
            {
                case "po":
                    c(v[0],v[1],"1");
                    break;
                case "ul":
                    c(v[0],v[1],"2");
                    break;
                case "ma":
                    c(v[0],v[1],"255");
                    break;
                case "gr":
                case "sa":
                case "sp":
                    c(v[0],v[1],"1.5");
                    break;
                case "lu":
                case "ne":
                    c(v[0],v[1],"3");
                    break;
                case "du":
                case "di":
                    c(v[0],v[1],"3.5");
                    break;
                case "mo":
                case "fa":
                    c(v[0],v[1],"4");
                    break;
                case "qu":
                    c(v[0],v[1],"5");
                    break;
                case "lo":
                    c(v[0],v[1],"8");
                    break;
                default:
                    new w("Not supported");
                    break;
            }
        }

        private double y(double v){return Convert.ToDouble(((double)1/(double)4096)*(v/Convert.ToDouble(1/4096)-(v%Convert.ToDouble(1/4096))));}

        private bool i(double v,double r,double b){if(((double)new Random().Next(0,(int)r))>b*v)return true;else return false;}

        private double f(double r, double h, double b){return 2.5*y((((3.0*h)-2.0)*r*b)/(3.0*h));}

        private void c(params string[] v)
        {
            var s =0.0;
            var x =0;
            if(int.Parse(v[1])>100&&int.Parse(v[1])<= 255){s =f(double.Parse(v[0]),double.Parse(v[1]),double.Parse(v[2]));x=0;}
            else if(int.Parse(v[0])>100&&int.Parse(v[0])<= 255){s =f(double.Parse(v[1]),double.Parse(v[0]),double.Parse(v[2]));x=1;}
            else
            {
                new w(String.Format("Which number is the Max HP? :{0} or {1}:",v[0],v[1]));
                var c_ = int.Parse(Console.ReadLine());
                s =f((double.Parse(v[0])+double.Parse(v[1]))-double.Parse(v[c_]),double.Parse(v[c_]),double.Parse(v[2]));
                x=2;
            }
            if (((double)new Random().Next(0, 2047))<s*2.5)new w("*shake*\nClick!");
            else
            {
                for(int c_= 0;c_<3;c_++)
                {
                    new w("*shake*");
                    var r =Math.Pow(65536.0/y(255.0/s),0.25);
                    if (i(r,double.Parse(v[x]),2.5)==true){new w("Click!");break;}else;
                }
            }
            Console.ReadKey();
        }
      }
  }

```
> -1 votes

---
Tags: code-golf
---


title: Programs that move around in memory

text:
# Question
Title: Programs that move around in memory
It's time for some quines! Well, sort of. This challenge is to create the smallest program that could move around in memory, i.e. if a program is resident in 2000:0100, the program should move to say, memory address be7a:3470.

## Rules

1. The memory address to move in should be pseudorandom.
2. It's still valid if it's a moving file around in the hard drive.
3. If it jumps around the RAM it should go to another segment in RAM.

I call these programs transposons, after the genes that move all around the DNA of an organism. Happy golfing! Contest ends May 9, 2014.

# Answer
# Bash , 12 bytes

Requires root permissions

```
mv /bin/mv ~

```

7 bytes if you already are in /bin

```
mv mv ~

```
> 0 votes

# Answer
## Bash, 2 bytes

```
$0

```

Moves itself to a new memory address when it is assigned a new process.

To move to a different spot on the harddrive it takes a few more:

```
cat $0>x

```
> 2 votes

# Answer
**COBOL** (Enterprise COBOL) One 72-character line, 11 significant characters

```
   ID DIVISION

```

That's the smallest (source) I can get which can be moved around (unless I need to make it shorter).

To do the moving:

```
   ID DIVISION
   PROCEDURE DIVISION
   CALL "GOLF006"
   CANCEL "GOLF006"
   CALL "GOLF006"

```

GOLF006 is the name of the stored program. This CALLs the program (using DYNAM compiler option to load the program dynamically), which program then returns to the CALLer having done its work. The second program then CANCELs the CALLed program (confusingly, CANCEL just causes the program to be "removed" from memory) and then CALLs the same program again, so a new one will be loaded.

I suspect the question will be updated soon...
> 0 votes

# Answer
# PHP (shamefully large):

```
<?file_put_contents(dirname($f=__FILE__).'/'.microtime(1).'.php',file_get_contents($f));unlink($f);

```

`file_put_contents($file,$content);`: write a file, create if it doesn't exist

`file_get_contents($file);`: read a file

`dirname($path)`: gives the directory name of a path

`microtime($float)`: returns a timestamp with microseconds (you can use `rand` or `mt_rand` here)

`unlink($file)`: deletes a link to a file, ultimately deleting a file is no other link exists

`__FILE__`: path of the current file being executed.
> 0 votes

---
Tags: code-golf
---


title: Lazy battleship placement

text:
# Question
Title: Lazy battleship placement
Imagine the following scenario: you are playing battleships with a friend but decide to cheat. Rather than moving a ship after he shoots where your ship used to be, you decide not to place any ships at all. You tell him all his shots are misses, until it is impossible to place ships in such a way.

You have to write a function, or a full program, that somehow takes 3 arguments: the field size, a list of amounts of ship sizes, and a list of shots.

### Battlefield

One of the given parameters is the board size. The battlefield is a square of cells, and the given parameter is simply one side of the square.
For example, the following is a board of size 5.

Coordinates on the field are specified as a 2-component string: a letter followed by a number. You can rely on the letters being in some particular case.
Letter specifies the column, number specifies the row of the cell (1-indexed). For example in the above picture, the highlighted cell is denoted by `"D2"`.
Since there are only 26 letters, the field can't be larger than 26x26.

### Ships

The ships are straight lines of 1 or more blocks. The amount of ships is specified in a list, where the first element is the amount of 1-cell ships, second - of 2-cell ships and so on.
For instance, the list `[4,1,2,0,1]` would create the following shipset:

When placed on the battlefield, ships cannot intersect, or even touch each other. Not even with corners. They can however touch the edges of the field.
Below you can see an example of valid ship placement:

You can assume that for a given shipset, there always exists a placement on an empty board of given size.

### Output

If such placements of ships exist, you have to output any of them.
The program has to output a newline-separated matrix of ascii characters of either of 3 types - one to denote blank cell, one - a ship piece, and one - a cell marked as "missed". No other characters should be output.
For example,

```
ZZ@Z
\@@Z
@\\Z
\Z\\

```

(In this example, I defined `@` to be blank cell, `\` to be a "missed" cell, and `Z` to be ship piece)

If no such placement exists, the program/function should return without outputting anything.

### Input

If you decide to make a fullblown program, it's up to specify you how the lists are input, some might go via arguments, some via stdin.

This is , lowest amount of characters wins.

An example non-golfed optimized solution can be found here
Compile with `-std=c99`, first argument is the size of the board, the other arguments are ship sizes. A newline-separated list of shots is given on stdin. Example:
`./a 4 1 1 1 <<< $'A2\nA4\nB3\nC3\nC4\D4'`

# Answer
> 2 votes
### GolfScript, 236 characters

```
n%([~](:N):M;[.,,]zip{~[)]*~}%-1%:S;{(65-\~(M*+}%:H;{{M*+}+N,/}N,%H-S[]]]{(~\.{(:L;{{M*+{+}+L,%}+N)L-,/}N,%{.{.M/\M%M*+}%}%{3$&,L=},{:K[{..M+\M-}%{..)\(}%3$\- 1$3$K+]}%\;\;\;\+.}{;:R;;;0}if}do{{{M*+.H?)'!'*\R?)'#'*'.'++1<}+N,/n}N,%}R!!*

```

The input is given on STDIN. First line contains size and number of ships, each following line coordinates of a single shot.

*Example:*

```
4 1 1 1
A2
A4
B3
C3
C4
D4

##.#
!..#
#!!#
!.!!

```

I thought that also this challenge should have at least one GolfScript answer. In the end it became very ungolfscriptish due to the used algorithm which favours performance over shortness.

*Annotated code:*

```
n%               # Split the input into lines
([~]             # The first line is evaluated to an array [N S1 S2 S3 ...]
(:N              # This happy smiley removes the first item and assigns it to variable N
):M;             # While this sad smiley increases N by one and assigns it to M

[.,,]zip         # For the rest of numbers in the first line create the array [[0 S1] [1 S2] [2 S3] ...]
{~[)]*~}%        # Each element [i Si] is converted into the list (i+1 i+1 ... i+1) with Si items.
-1%:S;           # Reverse (i.e. largest ship first) and assign the list to variable S.
                 # The result is a list of ship lengths, e.g. for input 3 0 2 we have S = [3 3 1 1 1].

{                # On the stack remains a list of coordinates
  (65-           # Convert the letter from A,B,... into numeric value 0,1,...
  \~(            # The number value is decreased by one
  M*+            # Both are combined to a single index (M*row+col)
}%:H;            # The list of shots is then assigned to variable H

                 # The algorithm is recursive backtracking implemented using a stack of tuples [A S R] where
                 #   - A is the list of open squares
                 #   - S is a list of ships to be placed
                 #   - R is the list of positions where ships were placed

    {{           # initial A is the full space of possible coordinates
      M*+        #   combine row and column values into a single index
    }+N,/}N,%    # do the N*N loop
    H-           # minus all places where a shot was done already
    S            # initial S is the original list
    []           # initial R is the empty list (no ships placed yet)
  ]
]                # The starting point is pushed on the stack

{                # Start of the loop running on the stack
  (~\            # Pop from the stack and extract items in order A R S

  .{             #   If S is non-empty

    (:L;         #     Take first item in S (longest ship) and asign its length to L

    {{M*+{+}+L,%}+N)L-,/}N,%{.{.M/\M%M*+}%}%
                 #     This lengthy expression just calculates all possible ship placements on a single board
                 #     (could be shortened by 3 chars if we don't respect board size but I find it clearer this way)

    {3$&,L=},    #     This step is just a filter on those placements. The overlap (&) with the list of open squares (3$)
                 #     must be of size L, i.e. all coordinates must be free

                 #     Now we have possible placements. For each one generate the appropriate tuple (A* S* R*) for recursion
    {
      :K         #     Assign the possible new ship placement to temporary variable K
      [
        {..M+\M-}%
        {..)\(}%
                 #       For each coordinate add the square one row above and below (first loop)
                 #       and afterwards for the resulting list also all squares left and right (second loop)
        3$\-     #       Remove all these squares from the list of available squares A in order to get the new A*
        1$       #       Reduced list of ships S* (note that the first item of S was already remove above)
        3$K+     #       Last item in tuple is R* = R + K, i.e. the ship's placements are added to the result
      ]
    }%

    \;\;\;       #     Discard the original values A R S
    \+           #     Push the newly generated tuples on the stack
    .            #     Loop until the stack is empty

  }{             #   else

    ;:R;;;       #     Assign the solution to the variable R and remove all the rest from the stack.
    0            #     Push a zero in order to break the loop

  }if            #   End if

}do              # End of the loop

{                # The output block starts here
  {{
    M*+
    .H?)         #   Is the current square in the list of shots?
    '!'*         #     then take a number of '!' otherwise an empty string
    \R?)         #   Is the current square in the list of ships?
    '#'*         #     then take a number of '#' otherwise an empty string
    '.'++        #   Join both strings and append a '.'
    1<           #   Take the first item of the resulting string, i.e. altogether this is a simple if-else-structure
  }+N,/n}N,%     # Do a N*N loop
}
R!!*             # Run this block only if R was assigned something during the backtracking.
                 # (!! is double-negation which converts any non-zero R into a one)
                 # Note: since the empty list from the algorithm is still on the stack if R wasn't assigned
                 # anything the operator !! works on the code block (which yields 1) which is then multiplied
                 # with the empty list.

```

# Answer
> 6 votes
# SWI-Prolog, ~~536~~ 4411 bytes

1 UNIX line ending, final new line not counted

The version with all optimizations removed (**441** bytes):

```
:-[library(clpfd)].
m(G,L):-maplist(G,L).
l(L,A):-length(A,L).
y(A,E,(X,Y)):-nth1(X,A,R),nth1(Y,R,F),var(F),F=E.
a(A,S):-l(L,A),X#>0,X#=<L,Y#>0,Y#=<L,h(S,(X,Y),A).
h(0,_,_).
h(L,(X,Y),A):-(B=A;transpose(A,T),B=T),y(B,s,(X,Y)),M#=L-1,Z#=Y+1,h(M,(X,Z),B).
e([],_,[]).
e([H|R],I,O):-J#=I+1,e(R,J,P),l(H,Q),Q ins I,append(P,Q,O).
r(R):-m(c,R),nl.
c(E):-var(E)->put(@);put(E).
g(L,H,S):-l(L,A),m(l(L),A),m(y(A,\),S),e(H,1,G),!,m(a(A),G),!,m(r,A).

```

Since the code is changed to minimize the number of bytes, it will no longer accept a list of shots that have duplicates.

---

The version with basic optimization, fully golfed (**536 → 506** bytes)

```
:-[library(clpfd)].
m(G,L):-maplist(G,L).
l(L,A):-length(A,L).
x(A,I,E):-X=..[a|A],arg(I,X,E).
y(A,E,(X,Y)):-x(A,X,R),x(R,Y,E).
a(A,S):-l(L,A),X#>0,X#=<L,Y#>0,Y#=<L,(B=A;transpose(A,T),B=T),h(S,(X,Y),B).
h(0,_,_).
h(L,(X,Y),A):-y(A,E,(X,Y)),var(E),E=s,M#=L-1,Z#=Y+1,h(M,(X,Z),A).
e([],_,[]).
e([H|R],I,O):-J#=I+1,e(R,J,P),l(H,Q),Q ins I,append(P,Q,O).
r(R):-m(c,R),nl.
c(E):-var(E)->put(@);put(E).
g(L,H,S):-l(L,A),m(l(L),A),sort(S,T),m(y(A,\),T),e(H,1,G),!,l(E,T),sumlist(G,D),L*L-E>=D,m(a(A),G),!,m(r,A).

```

I implement some basic checks (**count number of ship blocks necessary**) to make the code exits faster for clearly impossible cases. The code is also **immune to duplicate** in the list of shots so far.

---

Below is the (somewhat) readable version, with detailed comments:

```
:-[library(clpfd)].

% Shorthand for maplist, which works like map in high order function
m(G,L):-maplist(G,L).

% Creating a square matrix A which is L x L
board(L,A):-l(L,A),m(l(L),A).

% Shorthand for length, with order of parameters reversed
l(L,A):-length(A,L).

% Unification A[I] = E
x(A,I,E):-X=..[a|A],arg(I,X,E).

% Unification A[X][Y]=E
idx2(A,E,(X,Y)):-x(A,X,R),x(R,Y,E).

% Mark positions that have been shot
markshot(A,S):-m(idx2(A,\),S).

% Place all ships on the board
placeships(H,A):-m(placeship(A),H).

% Place a length S ship horizontal/vertical forward on the board
placeship(A,S):-
    l(L,A), % Get length
    X#>0,X#=<L,Y#>0,Y#=<L, % Constraint X and Y coordinates
    transpose(A,T), % Transpose to work on columns
    (placeship_h(S,(X,Y),A) ; placeship_h(S,(Y,X),T)).

% Place ship horizontal, forward at (X,Y)
placeship_h(0,_,_).
placeship_h(L,(X,Y),A):-
    idx2(A,E,(X,Y)),var(E),E=s, % Make sure position is unassigned, then mark
    L2#=L-1,Y2#=Y+1, % Do this for all blocks of the ship
    placeship_h(L2,(X,Y2),A).

% Expand the list of ships
% e.g. [2,3,1] --> [3,2,2,2,1,1]
shipexpand(S,O):-shipexpand(S,1,O).

shipexpand([],_,[]).
shipexpand([H|R],I,O):-
    I2#=I+1,shipexpand(R,I2,O2), % process the rest
    l(H,O1),O1 ins I, % duplicate current ship size H times
    append(O2,O1,O). % larger ship size goes in front

% Print the result
pboard(A):-m(prow,A).
prow(R):-m(pcell,R),print('\n').
pcell(E):-var(E)->print(@);print(E).

game(L,H,S):-
    board(L,A), % create board
    sort(S,SS), % remove duplicates
    markshot(A,SS), % mark positions that have been shot
    shipexpand(H,HH),!, % make a list of ships
    l(SC,SS),sumlist(HH,BC),L*L-SC>=BC, % check to speed-up, can be removed
    placeships(HH,A),!, % place ships
    pboard(A). % print result

```

Query format:

```
game(Board_Size, Ships_List, Shots_List).

```

Sample query (using the sample in the question):

```
?- game(4,[1,1,1],[(2,1),(3,2),(3,3),(4,1),(4,3),(4,4)]).
ssss
\ss@
@\\@
\@\\
true.

?- game(4,[2,2,0,1],[(2,1),(3,2),(3,3),(4,1),(4,3),(4,4)]).
ssss
\sss
s\\s
\s\\
true.

```

# Answer
> 5 votes
# Matlab - 536 chars

*Updated: Much smaller output formatting, some loop whitespace removed.*

*Updated: Added golfed version*

*Updated: Added commented version, reduced golfed version by ~100 chars*

```
% Battleship puzzle solver.
%
% n: size of the map (ex. 4 -> 4x4)
% sh: list of shots (ex. ['A2';'C4'])
% sp: ships of each size (ex. [2,0,1] -> 2x1 and 1x3)
%
function bs(n,sh,sp)

  % sp holds a vector of ship counts, where the index of each element is
  % the size of the ship. s will hold a vector of ship sizes, with order
  % not mattering. This is easier to work with using recursion, because
  % we can remove elements with Matlab's array subselection syntax, rather
  % than decrement elements and check if they're zero.
  %
  % Tricks:
  %   Since sp never contains a -1, find(1+sp) is the same as 1:length(sp)
  %   but is three characters shorter.
  %
  s=[];
  for i=find(1+sp)
    s(end+1:end+sp(i))=i;
  end

  % m will hold the map. It will be +2 in each direction, so that later we
  % can find neighbors of edge-spaces without checking bounds. For now,
  % each element is either '0' or '1' for a space or missed shot,
  % respectively. We convert the shots as provided by the user (ex. 'A2')
  % to marks on the map.
  %
  % Tricks:
  %   It takes one shorter character to subtract 47 than 'A' to determine
  %   the indices into the map.
  %
  m=zeros(n+2);
  for h=sh'
    m(h(2)-47,h(1)-63)=1;
  end

  % Solve the puzzle. q will either be the empty array or a solution map.
  %
  q=pp(m,s);

  % If a solution was found, output it, showing the original shots and the
  % ship placement. If no solution was found, print a sad face.
  %
  % Tricks:
  %   q is 0 on failure, which is treated like 'false'. q is a matrix on
  %   success which is NOT treated like 'true', so we have to check for
  %   failure first, then handle success in the 'else' block.
  %
  %   q contains the "fake shots" that surround each placed ship (see the
  %   pl function). We don't want to output those, so we just copy the ship
  %   markings into the original map.
  %
  if ~q ':('
  else
  m(find(q==2))=2;
  num2str(m(2:n+1,2:n+1),'%d')
  end

% Depth-first search for a solution.
%
% m: map (see main code above)
% s: vector of ship sizes to place in the map
%
% Returns q: square matrix of integers, updated with all requested ship
% sizes, or 0 if no solution is possible.
%
function q = pp(m,s)

  % If we have no ships to process, we're all done recursing and the
  % current map is a valid solution. Rather than handle this in an 'else'
  % block, we can assume it's the case and overwrite q if not, saving 4
  % characters.
  %
  q=m;

  % If we have any ships to place...
  %
  % Tricks:
  %   Since we are only interested in positive values in s, we can use
  %   sum(s) in place of isempty(s), saving 4 characters.
  %
  if sum(s)

    % Try to place the first ship in the list into the map, both vertically
    % (first call to p) and vertically (second call to p). We can process
    % any ship in the list, but the first can be removed from the list
    % with the fewest characters. r will hold a cell-array of options for
    % this ship.
    %
    r=[p(m,s(1),0),p(m',s(1),1)];

    % Recurse for each option until we find a solution.
    %
    % Tricks:
    %   Start with q, our return variable, set to 0 (indicating no solution
    %   was found. On each loop we'll only bother to recurse if q is still
    %   0. This relieves the need for if/else to check whether to continue
    %   the loop, or any final q=0 if the loop exits without success.
    %
    %   Sadly, there's no way around the length(r) call. Matlab doesn't
    %   provide syntax for iterating over cell-arrays.
    %
    q=0;
    for i=1:length(r)
      if ~q q=pp(r{i},s(2:end));end
    end
  end

% Place a single ship into a map.
%
% m: map (see main code above)
% s: ship size to place
% t: if the map has been transposed prior to this call
%
% Returns r: cell-array of possible maps including this ship
%
function r=p(m,s,t)
  % Start with an empty cell-array and pre-compute the size of the map,
  % which we'll need to use a few times.
  %
  r={};
  z=size(m);

  % For each row (omitting the first and last 'buffer' rows)...
  %
  for i=2:z(2)-1

  % For each starting column in this row where enough consecutive 0s
  % appear to fit this ship...
  %
  for j=strfind(m(i,2:end-1),(1:s)*0)

    % Copy the map so we can modify it without overwriting the variable
    % for the next loop.
    %
    n=m;

    % For each location on the map that is part of this optional
    % placement...
    for l=0:s-1
      % Let's leave this is an exercise for the reader ;)
      %
      v=-1:1;
      n([(l+j)*z(1)+i,z(1),1]*[ones(1,9);kron(v,[1 1 1]);[v v v]])=1;
    end

    % Mark each location that is part of this optional placement with
    % a '2'.
    %
    n(i,1+j:j+s)=2;

    % Since our results are going into a cell-array it won't be
    % convenient for the caller to undo any transpositions they might
    % have done. If the t flag is set, transpose this map back before
    % adding it to the cell-array.
    %
    if t n=n';end
    r{end+1}=n;
  end
  end

```

Here is the golfed version.

```
function bs(n,sh,sp)
s=[];for i=find(1+sp)
s(end+1:end+sp(i))=i;end
m=zeros(n+2);for h=sh'
m(h(2)-47,h(1)-63)=1;end
q=pp(m,s);if ~q ':('
else
m(find(q==2))=2;num2str(m(2:n+1,2:n+1),'%d')
end
function q = pp(m,s)
q=m;if sum(s)
r=[p(m,s(1),0),p(m',s(1),1)];q=0;for i=1:length(r)if ~q q=pp(r{i},s(2:end));end
end
end
function r=p(m,s,t)
r={};z=size(m);for i=2:z(2)-1
for j=strfind(m(i,2:end-1),(1:s)*0)n=m;for l=0:s-1
v=-1:1;n([(l+j)*z(1)+i,z(1),1]*[ones(1,9);kron(v,[1 1 1]);[v v v]])=1;end
n(i,1+j:j+s)=2;if t n=n';end
r{end+1}=n;end
end

```

Here's some samples.

```
>>bs(4,['A1';'B3'],[2,1])
1220
0000
2120
0000

>>bs(4,['A1';'B4'],[2,2])
1022
2000
0022
2100

>> bs(4,['A1';'B4';'C2'],[3,1])
1022
2010
0020
2100

>> bs(4,['A1';'B4';'C2'],[3,2])
:(

```

The big line with 'kron' (near the bottom of the un-golfed code) is my favorite part of this. It writes a '1' to all locations in the map that neighbor a given position. Can you see how it works? It uses the kronecker tensor product, matrix multiplication, and indexes the map as linear array...

# Answer
> 4 votes
## Python, 464 chars

```
B,L,M=input()
R=range(B)
C=B+1
M=sum(1<<int(m[1:])*C-C+ord(m[0])-65for m in M)
def P(L,H,S):
 if len(L)==0:
  for y in R:print''.join('.#!'[(S>>y*C+x&1)+2*(M>>y*C+x&1)]for x in R)
  return 1
 for s in[2**L[0]-1,sum(1<<C*j for j in range(L[0]))]:
  for i in range(C*C):
   if H&s==s and P(L[1:],H&~(s|s<<1|s>>1|s<<B|s>>B|s<<C|s>>C|s<<C+1|s>>C+1),S|s):return 1
   s*=2
 return 0
P(sum(([l+1]*k for l,k in enumerate(L)),[])[::-1],sum((2**B-1)<<B*j+j for j in R)&~M,0)

```

Input (stdin):

```
7, [4,1,2,0,1], ['A1','B2','C3']

```

Output:

```
!#####.
.!.....
##!###.
.......
###.#.#
.......
#.#....

```

Works using integers holding bitmaps of various features:

```
M = bitmap of misses
H = bitmap of holes where ships can still go
S = bitmap of ships already placed
L = list of ship sizes not yet placed
B = dimension of board
C = bitmap row length

```

# Answer
> 3 votes
# Python, 562 characters, -8 with ugly output, +4? for bash invocation

```
I=int;R=range
import sys;a=sys.argv
S=I(a[1]);f=[[0]*(S+2)for _ in R(S+2)]
C=a[2].split()
X=[]
for i,n in enumerate(C):X=[i+1]*I(n)+X
Q=a[3].split()
for q in Q:f[I(q[1:])][ord(q[0])-64]=1
D=R(-1,2)
V=lambda r,c:(all(f[r+Q][c+W]<2for Q in D for W in D),0,0)[f[r][c]]
def F(X):
 if not X:print"\n".join(" ".join(" .@"[c]for c in r[1:-1])for r in f[1:-1])
 x=X[0];A=R(1,S+1)
 for r in A:
    for c in A:
     for h in(0,1):
        def P(m):
         for i in R(x):f[(r+i,r)[h]][(c,c+i)[h]]=m
        if(r+x,c+x)[h]<S+2and all(V((r+i,r)[h],(c,c+i)[h])for i in R(x)):P(2);F(X[1:]);P(0)
F(X)

```

Note: the indent levels are space, tab, tab + space, tab + tab, and tab + tab + space. This saves a few characters from using spaces only.

**Usage and example**:

Takes input from command line arguments. Outputs a blank as a space, a shot as a `.`, and a `@` as part of a ship:

```
$ python bships_golf.py "7" "4 0 2 0 1" \
         "A1 C3 B5 E4 G6 G7 A3 A4 A5 A6 C1 C3 C5 C7 B6 B7 D1 D2 G3" 2>X
. @ . . @ @ @
  @   .
. @ . @   @ .
.     @ .
. . . @   @
. .   @     .
@ . . @   @ .

```

When unsolvable, prints nothing:

```
$ python bships_golf.py "3" "2" "A1 A3 B1 C1 C3" 2>X
. . .
@   @
.   .
$ python bships_golf.py "3" "2" "A1 A2 A3 B1 C1 C3" 2>X
$

```

The `2>X` is to suppress an error message since the program exits by throwing an exception. Feel free to add a +4 penalty if deemed fair. Otherwise I'd have to do a `try: ... except:0` to suppress it, which would take more characters anyway.

I can also print the output as numbers (`0`, `1`, and `2`) to shave off 8 characters, but I value aesthetics.

**Explanation**:

I represent the board as a list of lists of integers with size 2 greater than the input, to avoid having to do bounds checking. `0` represents an empty space, `1` a shot, and `2` a ship. I run through the shots list `Q` and mark all the shots. I convert the list of ships to an explicit list `X` of ships, e.g. `[4, 0, 2, 0, 1]` becomes `[5, 3, 3, 1, 1, 1, 1]`. Then it's a simple backtracking algorithm: in order of descending size order, try to place a ship, and then try to place the rest of the ships. If it doesn't work, try the next slot. As soon as it succeeds, the ship list `X` is null, and accessing `X[0]` throws an exception which quits the program. The rest is just heavy golfing (was initially 1615 characters).

# Answer
> 2 votes
# C# solution

```
  public static class ShipSolution {
    private static int[][] cloneField(int[][] field) {

      int[][] place = new int[field.Length][];

      for (int i = 0; i < field.Length; ++i) {
        place[i] = new int[field.Length];

        for (int j = 0; j < field.Length; ++j)
          place[i][j] = field[i][j];
      }

      return place;

    }

    private static void copyField(int[][] source, int[][] target) {
      for (int i = 0; i < source.Length; ++i)
        for (int j = 0; j < source.Length; ++j)
          target[i][j] = source[i][j];
    }

    // Check if placement a legal one
    private static Boolean isPlacement(int[][] field, int x, int y, int length, Boolean isHorizontal) {
      if (x < 0)
        return false;
      else if (y < 0)
        return false;
      else if (x >= field.Length)
        return false;
      else if (y >= field.Length)
        return false;

      if (isHorizontal) {
        if ((x + length - 1) >= field.Length)
          return false;

        for (int i = 0; i < length; ++i)
          if (field[x + i][y] != 0)
            return false;
      }
      else {
        if ((y + length - 1) >= field.Length)
          return false;

        for (int i = 0; i < length; ++i)
          if (field[x][y + i] != 0)
            return false;
      }

      return true;
    }

    //  When ship (legally) placed it should be marked at the field
    //  2 - ship itself
    //  3 - blocked area where no other ship could be placed
    private static void markPlacement(int[][] field, int x, int y, int length, Boolean isHorizontal) {
      if (isHorizontal) {
        for (int i = 0; i < length; ++i)
          field[x + i][y] = 2;

        for (int i = x - 1; i < x + length + 1; ++i) {
          if ((i < 0) || (i >= field.Length))
            continue;

          for (int j = y - 1; j <= y + 1; ++j)
            if ((j >= 0) && (j < field.Length))
              if (field[i][j] == 0)
                field[i][j] = 3;
        }
      }
      else {
        for (int i = 0; i < length; ++i)
          field[x][y + i] = 2;

        for (int i = x - 1; i <= x + 1; ++i) {
          if ((i < 0) || (i >= field.Length))
            continue;

          for (int j = y - 1; j < y + length + 1; ++j)
            if ((j >= 0) && (j < field.Length))
              if (field[i][j] == 0)
                field[i][j] = 3;
        }
      }
    }

    // Ship placement itteration
    private static Boolean placeShips(int[][] field, int[] ships) {
      int[] vessels = new int[ships.Length];

      for (int i = 0; i < ships.Length; ++i)
        vessels[i] = ships[i];

      for (int i = ships.Length - 1; i >= 0; --i) {
        if (ships[i] <= 0)
          continue;

        int length = i + 1;

        vessels[i] = vessels[i] - 1;

        // Possible placements
        for (int x = 0; x < field.Length; ++x)
          for (int y = 0; y < field.Length; ++y) {
            if (isPlacement(field, x, y, length, true)) {
              int[][] newField = cloneField(field);

              // Mark
              markPlacement(newField, x, y, length, true);

              if (placeShips(newField, vessels)) {
                copyField(newField, field);

                return true;
              }
            }

            if (length > 1)
              if (isPlacement(field, x, y, length, false)) {
                int[][] newField = cloneField(field);

                // Mark
                markPlacement(newField, x, y, length, false);

                if (placeShips(newField, vessels)) {
                  copyField(newField, field);

                  return true;
                }
              }
          }

        return false; // <- the ship can't be placed legally
      }

      return true; //    <- there're no more ships to be placed
    }

    /// <summary>
    /// Solve ship puzzle
    /// </summary>
    /// <param name="size">size of the board</param>
    /// <param name="ships">ships to be placed</param>
    /// <param name="misses">misses in (line, column) format; both line and column are zero-based</param>
    /// <returns>Empty string if there is no solution; otherwise possible ship placement where
    ///   . - Blank place
    ///   * - "miss"
    ///   X - Ship
    /// </returns>
    public static String Solve(int size, int[] ships, String[] misses) {
      int[][] field = new int[size][];

      for (int i = 0; i < size; ++i)
        field[i] = new int[size];

      if (!Object.ReferenceEquals(null, misses))
        foreach (String item in misses) {
          String miss = item.Trim().ToUpperInvariant();

          int x = int.Parse(miss.Substring(1)) - 1;
          int y = miss[0] - 'A';

          field[x][y] = 1;
        }

      if (!placeShips(field, ships))
        return "";

      StringBuilder Sb = new StringBuilder();

      foreach (int[] line in field) {
        if (Sb.Length > 0)
          Sb.AppendLine();

        foreach (int item in line) {
          if (item == 1)
            Sb.Append('*');
          else if (item == 2)
            Sb.Append('X');
          else
            Sb.Append('.');
        }
      }

      return Sb.ToString();
    }
  }

  ...

  int size = 4;
  int[] ships = new int[] { 1, 1, 1 };
  String[] misses = new String[] {"C1", "C2", "B2", "A3", "A1", "B3", "D1"};

  // *X**
  // .**X
  // **.X
  // XX.X
  Console.Out.Write(ShipSolution.Solve(size, ships, misses));

```

# Answer
> 2 votes
## Perl, ~~455 447 437 436 422~~ 418

```
$n=($N=<>+0)+1;@S=map{(++$-)x$_}<>=~/\d+/g;$_=<>;$f=('~'x$N.$/)x$N;substr($f,$n*$1-$n-65+ord$&,1)=x while/\w(\d+)/g;sub f{for my$i(0..$N*$n-1){for(0..@_-2){my($f,@b)=@_;$m=($s=splice@b,$_,1)-1;pos=pos($u=$_=$f)=$i;for(s/\G(~.{$N}){$m}~/$&&("\0"."\377"x$N)x$s|(o."\0"x$N)x$m.o/se?$_:(),$u=~s/\G~{$s}/o x$s/se?$u:()){for$k(0,$N-1..$n){s/(?<=o.{$k})~|~(?=.{$k}o)/!/sg}return$:if$:=@b?f($_,@b):$_}}}}$_=f$f,@S;y/!/~/;print

```

Indented:

```
$n=($N=<>+0)+1;
@S=map{(++$-)x$_}<>=~/\d+/g;
$_=<>;
$f=('~'x$N.$/)x$N;
substr($f,$n*$1-$n-65+ord$&,1)=x while/\w(\d+)/g;
sub f{
    for my$i(0..$N*$n-1){
        for(0..@_-2){
            my($f,@b)=@_;
            $m=($s=splice@b,$_,1)-1;
            pos=pos($u=$_=$f)=$i;
            for(s/\G(~.{$N}){$m}~/
              $&&("\0"."\377"x$N)x$s|(o."\0"x$N)x$m.o/se?$_:(),
              $u=~s/\G~{$s}/o x$s/se?$u:()){
                for$k(0,$N-1..$n){
                    s/(?<=o.{$k})~|~(?=.{$k}o)/!/sg
                }
                return$:if$:=@b?f($_,@b):$_
            }
        }
    }
}
$_=f$f,@S;
y/!/~/;
print

```

I expect it can be golfed further (e.g. with `eval<>` for pre-formatted input, as I see it's OK (?)), and also some other things (50 `$` sigils? no, they'll stay).

Speed, as I said earlier, can be an issue (from instantaneous (see example below) to very-very long), depending on where the solution is on recursion tree, but let it be the question of obsolescence of hardware used. I'll do optimized version later, with recursion gone and 2-3 other obvious tricks.

It's run like this, 3 lines being fed through STDIN:

```
$ perl bf.pl
7
4 1 2 0 1
A1 B2 C3
xo~o~o~
~x~~~~~
o~xo~o~
~~~o~o~
o~~~~o~
o~~~~~~
o~ooooo

```

`~` is the ocean (artistic solution, isn't it), `o`'s and `x`s are ships and shots. First 5 lines get the input and prepare our 'battlefield'. `$N` is size, `@S` is unrolled array of ships (e.g. `1 1 1 1 2 3 3 5` as above), `$f` is a string representing battlefield (rows with newlines concatenated). Next is recursive subroutine, which expects current battlefield state and list of remaining ships. It checks left to right, top to bottom and tries to place each ship in each position, both horizontally and vertically (see? Ripe to optimize, but that'll be later). Horizontal ship is obvious regexp replacement, vertical a bit trickier -- bitwise string manipulation to replace in 'column'. On success (H, V or both), new inaccessible positions are marked with `!`, and it forks to next iteration. And so on.

**Edit:** OK, here's **594** bytes (when un-indented) version that actually tries to be useful (i.e. fast) - optimized to the best of my ability while still implementing the same techniques - recursion (albeit done 'manually') and regexps. It maintains a 'stack' - `@A` \- array of states worth to investigate. A 'state' is 4 variables: current battlefield string, index from where to start trying to place ships, reference to array of remaining ships, and index of next ship to try. Initially there's a single 'state' - start of empty string, all ships. On match (H or V, see above), current state is pushed to investigate later, updated state (with a ship placed and inaccessible positions marked) is pushed and block is restarted. When end of battlefield string is reached without success, next available state from `@A` is investigated (if any).

Other optimizations are: not restarting from the very beginning of the string, trying to place large ships first, not checking ship of same size if previous one failed in the same position, + maybe something else (like no `$&` variable etc.).

```
$N=<>+0;
$S=[reverse map{(++$-)x$_}<>=~/\d+/g];
$_=<>;
$f=('~'x$N.$/)x$N;
substr($f,$N*$2-$N+$2-66+ord$1,1)=x while/(\w)(\d+)/g;
push@A,$f,0,$S,0;
O:{
    ($f,$i,$S,$m)=splice@A,-4;
    last if!@$S;
    F:{
        for$j($m..$#$S){
            next if$j and$$S[$j]==$$S[$j-1];
            $s=$$S[$j];
            my@m;
            $_=$f;
            $n=$s-1;
            pos=$i;
            push@m,$_ if s/\G(?:~.{$N}){$n}~/
                ${^MATCH}&("\0"."\377"x$N)x$s|(o."\0"x$N)x$n.o/pse;
            $_=$f;
            pos=$i;
            push@m,$_ if s/\G~{$s}/o x$s/se;
            if(@m){
                push@A,$f,$i,$S,$j+1;
                my@b=@$S;
                splice@b,$j,1;
                for(@m){
                    for$k(0,$N-1..$N+1){
                        s/(?<=o.{$k})~|~(?=.{$k}o)/!/gs
                    }
                    push@A,$_,$i+1,\@b,0
                }
                redo O
            }
        }
        redo if++$i-length$f
    }
    redo if@A
}
print@$S?'':$f=~y/!/~/r

```

.

```
perl bf+.pl
10
5 4 3 2 1
A1 B2 C3 A10 B9 C10 J1 I2 H3 I9 J10 A5 C5 E5 F6 G7
xooooo~oox
~x~~~~~~x~
ooxooooxo~
~~~~~~~~o~
xoxoxoo~o~
~o~o~x~~o~
~o~o~ox~~~
~~~~~o~ooo
oxo~~~~~x~
x~x~o~o~ox

```

OTOH, it still takes forever for impossible case `6 5 4 3 2 1` in example above. Maybe practical version should exit immediately if total ship tonnage exceeds battlefield capacity.

# Answer
> 1 votes
# Java, 1178

Yeah much too long .\_.

```
import java.util.*;class S{public static void main(String[]a){new S();}int a;int[][]f;List<L>l;Stack<Integer>b;S(){Scanner s=new Scanner(System.in);a=s.nextInt();f=new int[a][a];for(int[]x:f)Arrays.fill(x,95);s.next(";");b=new Stack();for(int i=1;s.hasNextInt();i++){b.addAll(Collections.nCopies(s.nextInt(),i));}s.next(";");while(s.findInLine("([A-Z])")!=null)f[s.match().group(1).charAt(0)-65][s.nextInt()-1]=79;l=new ArrayList();for(int i=0;i<a;i++){l.add(new L(i){int g(int c){return g(c,i);}void s(int c,int v){f[c][i]=v;}});l.add(new L(i){int g(int r){return g(i,r);}void s(int r,int v){f[i][r]=v;}});}if(s()){String o="";for(int r=0;r<a;r++){for(int c=0;c<a;c++)o+=(char)f[c][r];o+='\n';}System.out.print(o);}}boolean s(){if(b.empty())return true;int s=b.pop();Integer n=95;for(L c:l){int f=0;for(int x=0;x<a;x++){if(n.equals(c.g(x)))f++;else f=0;if(f>=s){for(int i=0;i<s;i++)c.s(x-i,35);if(s())return true;for(int i=0;i<s;i++)c.s(x-i,n);}}}b.push(s);return false;}class L{int i;L(int v){i=v;}void s(int i,int v){}int g(int i){return 0;}int g(int c,int r){int v=0;for(int x=-1;x<2;x++)for(int y=-1;y<2;y++)try{v|=f[c+x][r+y];}catch(Exception e){}return v&(f[c][r]|32);}}}

```

Ungolfed:

```
import java.util.*;

class S {
    public static void main(String[] a) {
        new S();
    }

    /**
     * Number of rows/columns
     */
    int a;

    /**
     * A reference to the full field
     */
    int[][] f;

    /**
     * List of Ls representing all columns/rows
     */
    List<L> l;

    /**
     * Stack of all unplaced ships, represented by their length as Integer
     */
    Stack<Integer> b;

    S() {
        // Read input from STDIN:
        Scanner s = new Scanner(System.in);
        a = s.nextInt();
        f = new int[a][a];
        // initialize field to all '_'
        for(int[] x: f)
            Arrays.fill(x, 95);
        // ; as separator
        s.next(";");
        b = new Stack();
        // Several int to represent ships
        for (int i = 1; s.hasNextInt(); i++) {
            // nCopies for easier handling (empty Stack => everything placed)
            b.addAll(Collections.nCopies(s.nextInt(), i));
        }
        // ; as separator
        s.next(";");
        // find an uppercase letter on this line
        while (s.findInLine("([A-Z])") != null) {
            // s.match.group(1) contains the matched letter
            // s.nextInt() to get the number following the letter
            f[s.match().group(1).charAt(0) - 65][s.nextInt() - 1] = 79;
        }
        // Loop is left when line ends or no uppercase letter is following the current position

        // Now create a List of Lists representing single columns and rows of our field
        l = new ArrayList();
        for (int i = 0; i < a; i++) {
            l.add(new L(i) {
                int g(int c) {
                    return g(c, i);
                }

                void s(int c, int v) {
                    f[c][i] = v;
                }
            });
            l.add(new L(i) {
                int g(int r) {
                    return g(i, r);
                }

                void s(int r, int v) {
                    f[i][r] = v;
                }
            });
        }
        // try to place all ships
        if (s()) {
            // print solution
            String o = "";
            for (int r = 0; r < a; r++) {
                for (int c = 0; c < a; c++) {
                    o += (char) f[c][r];
                }
                o += '\n';
            }
            System.out.print(o);
        }
    }

    /**
     * Try to place all ships
     *
     * @return {@code true}, if a solution is found
     */
    boolean s() {
        if (b.empty()) {
            // no more ships
            return true;
        }
        // take a ship from the stack
        int s = b.pop();
        // 95 is the Ascii-code of _
        Integer n = 95;
        // go over all columns and rows
        for (L c : l) {
            // f counts the number of consecutive free fields
            int f = 0;
            // move through this column/row
            for (int x = 0; x < a; x++) {
                // Is current field free?
                if (n.equals(c.g(x))) {
                    f++;
                } else {
                    f = 0;
                }
                // Did we encounter enough free fields to place our ship?
                if (f >= s) {
                    // enter ship
                    for (int i = 0; i < s; i++) {
                        c.s(x - i, 35);
                    }
                    // try to place remaining ships
                    if (s()) {
                        return true;
                    }
                    // placing remaining ships has failed ; remove ship
                    for (int i = 0; i < s; i++) {
                        c.s(x - i, n);
                    }
                }
            }
        }
        // we have found no place for our ship so lets push it back
        b.push(s);
        return false;
    }

    /**
     * List representing a single row or column of the field.
     * "Abstract"
     */
    class L {
        /**
         * Index of row/column. Stored here as loop-variables can not be final. Used only {@link #g(int)} and {@link #s(int, int)}
         */
        int i;

        L(int v) {
            i = v;
        }

        /**
         * Set char representing the state at the i-th position in this row/column.
         * "Abstract"
         */
        void s(int i, int v) {
        }

        /**
         * Get char representing the state at the i-th position in this row/column.
         * "Abstract"
         *
         * @return {@code '_'} if this and all adjacent field contain no {@code '#'}
         */
        int g(int i) {
            return 0;
        }

        /**
         * Get char representing the state at the position in c-th column and r-th row
         *
         * @return {@code '_'} if this and all adjacent field contain no {@code '#'}
         */
        int g(int c, int r) {
            // v stores the result
            int v = 0;
            // or all adjacent fields
            for (int x = -1; x < 2; x++) {
                for (int y = -1; y < 2; y++) {
                    // ungolfed we should use something like
                    // v |= 0 > c + x || 0 > r + y || c + x >= a || r + y >= a ? 0 : f[c + x][r + y];
                    // but his will do (and is shorter)
                    try {
                        v |= f[c + x][r + y];
                    } catch (Exception e) {
                    }
                }
            }
            // we use '_' (95), 'O' (79), '#' (35). Only 35 contains the 32-bit
            // So we only need the 32-bit of the or-ed-value + the bits of the value directly in this field
            return v & (f[c][r] | 32);
        }

    }
}

```

Sample-Input

> ```
> 6 ; 3 2 1 ; A1 A3 B2 C3 D4 E5 F6 B6 E3 D3 F4
>
> ```

Sample-Output

> ```
> O###_#
> _O____
> O_OOO#
> #_#O_O
> #_#_O#
> _O___O
>
> ```

With

* `O` missed shot
* `#` ship-part
* `_` shoot here next ;-)

See on ideone.com

Input-handling expects the spaces around numbers / `;` and won't work otherwise.

I am placing big ships first as they have fewer places to go. If you want to switch to small-first you can replace `pop()` by `remove(0)` and `push(s)` by `add(0,s)` even replacing only one of the two should still result in a valid program.

If you allow ships touching each other the `g(int,int)` function can be vastly simplified or removed.

---
Tags: code-golf, combinatorics
---


title: Create a random 3D asteroid

text:
# Question
Title: Create a random 3D asteroid
Imagine you are working on a 3D adaptation of the classical video game Asteroids. Your task is to write an algorithm that can create a random 3D asteroid.

This is a popularity contest, not code golf. Write nice code and create interesting results. Add other cool features if you want.

Rules:

* Your algorithm must actually create the model, not just load it from an external source or similar.
* The results must be (pseudo-)random. Running the algorithm several times must create different results.
* Real-time capability is desirable, but not necessary.
* Low or high polygon count? Realistic or stylized? You decide...
* The output must be a mesh, either in memory or as a file such as Wavefront OBJ. In either case you need to render it in some way.
* Explain your algorithm, so that everybody can learn from it.
* Show some images of your results.

# Answer
# Blender + Python

Blender's built-in Python scripting is perfect for this sort of thing.

Open a Python console and paste in the following:

```
import bpy
import random

def asteroid():
    bpy.ops.mesh.primitive_ico_sphere_add()
    bpy.ops.object.mode_set(mode='EDIT')
    bpy.ops.mesh.faces_shade_smooth()
    bpy.ops.mesh.select_mode(type='VERT')
    bpy.ops.mesh.select_random()
    bpy.ops.transform.resize(value=(random.uniform(1.1,1.4),random.uniform(1.1,1.4),random.uniform(1.1,1.4)))
    bpy.ops.mesh.select_all(action='SELECT')
    bpy.ops.mesh.subdivide(smoothness=1)
    bpy.ops.mesh.select_random()
    bpy.ops.transform.resize(value=(random.uniform(1.05,1.15),random.uniform(1.05,1.15),random.uniform(1.05,1.15)))
    bpy.ops.mesh.select_all(action='SELECT')
    bpy.ops.mesh.subdivide(smoothness=1)
    bpy.ops.mesh.select_random()
    bpy.ops.transform.resize(value=(random.uniform(0.92,1.05),random.uniform(0.92,1.05),random.uniform(0.92,1.05)))
    bpy.ops.mesh.select_all(action='SELECT')
    bpy.ops.mesh.subdivide(smoothness=1)
    stretch = random.uniform(0.9,1.5)
    bpy.ops.transform.resize(value=(stretch,1,1))
    bpy.ops.transform.rotate(value=(random.uniform(-1.57,1.57)), axis=(random.uniform(-1.57,1.57),random.uniform(-1.57,1.57),random.uniform(-1.57,1.57)))
    bpy.ops.object.mode_set(mode='OBJECT')

asteroid()

```

An asteroid will then be created at the position of your 3D cursor:

Want another asteroid? Move the 3D cursor somewhere else and then type `asteroid()` into the Python console again (or just `Enter` to repeat the last line entered).

To make it look more like a piece of space rock and less like a blob of plastic, you need to apply a suitable material. The following procedural material works quite well. I used a diffuse colour of `#635C5B`, and `#8D887F` in the marble texture.

**How it works:**

1. Start by creating a simple icosahedron (`bpy.ops.mesh.primitive_ico_sphere_add()`).
2. Enter edit mode (`bpy.ops.object.mode_set(mode='EDIT')`) and apply smooth shading so that the individual facets blend into one another (`bpy.ops.mesh.faces_shade_smooth()`).
3. Select a random subset of the object's vertices (`bpy.ops.mesh.select_random()`).
4. Scale them randomly in the X, Y and Z directions (`bpy.ops.transform.resize()`).
5. Select the whole object (`bpy.ops.mesh.select_all(action='SELECT')`) and apply smooth subdivision to add new vertices by interpolating smoothly across the deformed object (`bpy.ops.mesh.subdivide(smoothness=1)`).
6. (Repeat steps 3–5 a couple more times.)
7. Stretch the object in the X direction to make it a bit less spherical (`bpy.ops.transform.resize(value=(stretch,1,1))`)
8. Apply a random rotation transform (`bpy.ops.transform.rotate()`)
9. Finally, exit edit mode and leave the object selected (`bpy.ops.object.mode_set(mode='OBJECT')`).

**More examples:**
> 30 votes

---
Tags: popularity-contest, graphical-output
---


title: Determine the critical path

text:
# Question
Title: Determine the critical path
In project management there's a method, called the critical path method, that is used for scheduling activities and for determining which activities' timings are crucial (i.e. critical) and for which activities the schedule offers a timing tolerance.

Your program's task is to order a set of activities chronologically and for each of those activities determine their:

* earliest possible start;
* earliest possible finish;
* latest possible start;
* latest possible finish.

Lastly, your program should mark which subsequent activities make up the longest, uninterrupted path; i.e. the critical path.

The input will be the activities by their name, with their duration (in an unspecified time unit) and with the names of the activities they depend on. For this challenge only so-called *finish to start* dependencies will be presented as input. In other words: any possibly provided dependencies for a given activity signify that said activity can only start when all the activities, that this activity depends on, have finished. No other forms of dependencies will be presented.

The expected input is in the form of (possibly multiples of):

`[F:12;C,B]`

Where:

* `F` signifies the activity's name; an uppercase alphabetic character;
* `12` signifies the duration as a positive integer;
* `C,B` signifies the optional dependencies, as a comma-separated list of activity names.

Here's an example input:

`[A:15][B:7][C:9;A,B][D:3;B,C][E:5;C][F:11;D][G:4;D,E,F]`

Meaning:

```
 name | duration | dependencies
------+----------+--------------
    A |       15 |
    B |        7 |
    C |        9 |          A,B
    D |        3 |          B,C
    E |        5 |            C
    F |       11 |            D
    G |        4 |        D,E,F

```

Your program's output will be an ASCII table, in the *exact* following form, but filled with different data, depending on the input of course (here I'm using the example input, from above, as input):

```
 name | estart | efinish | lstart | lfinish | critical
------+--------+---------+--------+---------+----------
    A |      0 |      15 |      0 |      15 |        Y
    B |      0 |       7 |      8 |      15 |        N
    C |     15 |      24 |     15 |      24 |        Y
    D |     24 |      27 |     24 |      27 |        Y
    E |     24 |      29 |     33 |      38 |        N
    F |     27 |      38 |     27 |      38 |        Y
    G |     38 |      42 |     38 |      42 |        Y

```

Where:

* the activities are ordered chronologically ascending by `estart` (and then arbitrarily);
* `estart` is earliest start;
* `efinish` is earliest finish;
* `lstart` is latest start;
* `lfinish` is latest finish;
* `critical` is a `Y/N` value, signifying whether this activity belongs to the critical path (i.e. `lstart - estart = 0` and `lfinish - efinish = 0`).

The expected constraints for the input will be:

* The activity names will never exceed `Z`; i.e. the total amount of activities will never exceed 26;
* The total duration (i.e. the latest finish of the last activity) will never exceed `9999999` (the width of the `lfinish` column, with padding);
* The number of dependencies, for any given activity, will never exceed 6;
* The input will never be inconsistent (e.g. no non-existent dependencies, etc.).

The constraints for your program are:

* No use of existing PM/CPM APIs1; you must create the algorithm from scratch.

This is a 2; the most elegant solution (or at least, I hope that's what voters will vote for), by popular vote, wins. The winner will be determined 4 days after the submission time of this challenge.

---

 1. If any such API even exists.
2. I want to give the more verbose languages a fair shot at this as well.

# Answer
### GolfScript

A GolfScript solution - just because it can be done.

```
# Parse input
'['-']'%:I{[.1<\2>';'/(~\{','/{`{\1<=}+I?I?}/}%0]}%

# Determine estart iteratively
{:A{[~{A=~@+\;\;}2$%+$-1=]}%.A=!}do

# Invert dependencies
A{~@+\;\;}%$-1=:M;
[.,,]zip{[~{\~\2=@?0<{;}*}+[A.,,]zip%\:^~;;@^3=M]}%

# Determine lfinish iteratively
{:A{[~{A=~\;\;\-\;}3$%+$0=]}%.A=!}do

# Print results

# Formats numbers (right aligned, 7 chars)
{`"       "\+-7>}:F;

" name | estart | efinish | lstart | lfinish | critical \n"
"------+--------+---------+--------+---------+----------\n"
@{"    "\(" |"@.2=F" | "@.~;@+\;F" |"@.~\;\;\-F" | "@.3=F" |        "@~-\;+!"NY"1/=n}%

```

Example (online):

```
> [A:15][B:7][C:9;A,B][D:3;B,C][E:5;C][F:11;D][G:4;D,E,F]

 name | estart | efinish | lstart | lfinish | critical
------+--------+---------+--------+---------+----------
    A |      0 |      15 |      0 |      15 |        Y
    B |      0 |       7 |      8 |      15 |        N
    C |     15 |      24 |     15 |      24 |        Y
    D |     24 |      27 |     24 |      27 |        Y
    E |     24 |      29 |     33 |      38 |        N
    F |     27 |      38 |     27 |      38 |        Y
    G |     38 |      42 |     38 |      42 |        Y

```
> 4 votes

# Answer
## C#, many many characters.

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

namespace ConsoleApplication2
{
    class Program
    {
        static char[] COLON = { ':' };
        static char[] SEMI_COLON = { ';' };
        static char[] COMMA = { ',' };
        static char[] BRACE = { ']' };

        static void Main(string[] args)
        {
            int step = 0;

            List<Activity> i = new List<Activity>();
            Console.Write("Enter input: ");
            string s = Console.ReadLine().Replace("[", null);
            foreach (string x in s.Split(BRACE, StringSplitOptions.RemoveEmptyEntries))
            {
                string[] y = x.Split(SEMI_COLON);
                Activity n = new Activity(x.Split(COLON)[0], Int32.Parse(y[0].Split(COLON)[1]));
                n.Name = x.Split(COLON)[0];
                n.Dependencies = (y.Length > 1) ? y[1].Split(COMMA).ToList() : new List<string>();
                i.Add(n);
            }

            do
            {
                List<string> d = i.Where(x => x.Done()).Select(y => y.Name).ToList();
                foreach (Activity working in i.Where(x => x.Dependencies.Except(d).Count() == 0 && !x.Done())) working.Step(step);
                step++;
            } while (i.Count(x => !x.Done()) > 0);

            foreach (Activity a in i)
            {
                Activity next = i.OrderBy(x => x.EFinish).Where(x => x.Dependencies.Contains(a.Name)).FirstOrDefault();
                a.LFinish = (next == null) ? a.EFinish : next.EStart;
                a.LStart = a.LFinish - a.Duration;
            }

            Console.WriteLine(" name | estart | efinish | lstart | lfinish | critical");
            Console.WriteLine("------+--------+---------+--------+---------+----------");
            foreach (Activity a in i)
            {
                Console.Write(a.Name.PadLeft(5) + " |");
                Console.Write(a.EStart.ToString().PadLeft(7) + " |");
                Console.Write(a.EFinish.ToString().PadLeft(8) + " |");
                Console.Write(a.LStart.ToString().PadLeft(7) + " |");
                Console.Write(a.LFinish.ToString().PadLeft(8) + " |");
                string critical = (a.LFinish - a.EFinish == 0 && a.LStart - a.EStart == 0) ? "Y" : "N";
                Console.WriteLine(critical.PadLeft(9));
            }
            Console.WriteLine("Hit any key to exit.");
            Console.ReadKey();
        }
    }

    class Activity
    {
        public string Name {get ; set;}
        public int Duration {get ; set;}
        public List<string> Dependencies {get ; set;}
        public int EStart {get ; set;}
        public int EFinish {get ; set;}
        public int LStart { get; set; }
        public int LFinish { get; set; }
        private int steps = 0;

        public Activity(string name, int time)
        {
            EStart = -1;
            EFinish = 0;
            LStart = 0;
            LFinish = 0;
            Name = name;
            Duration = time;
            steps = time;
        }

        public void Step(int count)
        {
            EStart = (EStart == -1) ? count : EStart;
            if (--steps == 0) EFinish = count + 1;
        }

        public bool Done()
        {
            return steps == 0;
        }
    }
}

```

I would hesitate to call this "the most elegant solution", but it trades the verbosity of C# for ease of parsing input and formatting output (and has Linq).

I basically just loops through all of the activities and increments a time counter if all their dependencies have been completed until all of them are done. That gives the earliest starts and earliest finishes. The latest finish for each is simply the earliest start among activities that have it as a dependency, and the latest start is the activity duration minus the latest start.
> 1 votes

# Answer
# Haskell, 39 LoC

```
import Control.Exception.Base (assert)
import Data.List
import Data.Maybe (fromJust)
import Text.Printf

splitBefore x = groupBy (\_ y -> x /= y)

data Activity = Activity {aName :: Char, aLength :: Int, depNames :: [Char]}
                deriving (Eq, Ord, Show)

instance Read Activity where
  readsPrec _ ('[' : aName : ':' : rest1) =
    let [(aLength, rest2)] = reads rest1 :: [(Int, String)]
        (rest3, ']':rest) = span (/= ']') rest2
        depNames = map (\[_,x] -> x) $ splitBefore ',' $ rest3
    in  [(Activity {aName = aName, aLength = aLength, depNames = depNames},rest)]

main = getLine >>= putStrLn . \input ->
  let activities = map read $ splitBefore '[' $ input :: [Activity]
      activityByName a = fromJust . find ((a ==) . aName) $ activities
      dependencies = map activityByName . depNames
      dependents a = filter ((a `elem`) . dependencies) $ activities
      estart   a = case dependencies a of
                     [] -> 0
                     ds -> maximum $ map efinish ds
      efinish  a = estart a + aLength a
      critLength = maximum $ map efinish $ activities
      lfinish  a = case dependents a of
                     [] -> critLength
                     ds -> minimum $ map lstart ds
      lstart   a = lfinish a - aLength a
      critical a = estart a == lstart a
      format   a = printf " %4c | %6d | %7d | %6d | %7d | %8c "
                     (aName a) (estart a) (efinish a) (lstart a) (lfinish a)
                     (if critical a then 'Y' else 'N')

  in  unlines $ " name | estart | efinish | lstart | lfinish | critical "
              : "------+--------+---------+--------+---------+----------"
              : map format activities

```
> 1 votes

---
Tags: popularity-contest, optimization
---


title: The Floating Horde

text:
# Question
Title: The Floating Horde
**Introduction**

The rain finally subsided. Most of humanity drowned due to a bug in @user12345's code. Survivors are scattered across a worldwide archipelago. Radio communication is up, and humanity is poised to thrive once more. For no reason whatsoever, zombie pirates have gathered at the Prime Meridian, and are sweeping westward. The horde devours all.

**Problem**

Our doomsday scenario can be described by 5 integers on a single line which represent a set of cooperating island communities. They are ordered from west (leftmost integer) to east (rightmost integer).

Beginning with the island farthest east, islanders flee in pairs to the next closest island. Curiously, for each pair that embarks, only one of them ever survives the trip. Islanders *only* travel in pairs. Odd populations elect a sole inhabitant to stay behind and provide the latest radio updates on the antics of the zombie pirate horde. Populations refuse to travel until all islands to the east of them have completed their migrations or died. When the population reaches the final, westernmost island, travel ceases.

The operations manager at the end of the world needs a program that can output the final population counts of each village.

**Example Input**

`3 8 6 0 2`

**Example Output**

`8 1 0 1 0`

**Assumptions**

* Input may be provided via stdin, read from an arbitrarily named file, or accepted as an argument
* For each island, 0 \<= population \<= 1024
* Populations never skip an island

Shortest answer wins!

# Answer
> 26 votes
### APL, 16 characters

```
{(1e9,4⍴2)⊤2⊥⍎⍵}

```

The input is provided as string to this block:

```
{(1e9,4⍴2)⊤2⊥⍵} "3 8 6 0 2"
8 1 0 1 0

```

or one char less if the input is provided as argument to this block:

```
{(1e9,4⍴2)⊤2⊥⍵} 3 8 6 0 2
8 1 0 1 0

```

It is based on the idea of Ilmari Karonen in this comment.

* `2⊥⍵` does a base 2 conversion of the input.
* `(1e9,4⍴2)⊤` thus converts this number back into base 2 (for the four last digits) and base 1e9 for the first, which is enough for the input ranges given above. (`1e9,4⍴2` builds the list `1e9 2 2 2 2`.)

Note that the fleeing west is done automatically by the base conversion during this process.

# Answer
> 13 votes
### GolfScript, 23 22 characters

```
~]{{.2/@+\2%}*]}4*' '*

```

An iterative approach. The array is iterated several times and each time a number of pairs is transferred from right to left. Try the example online.

*Short explanation of the code:*

```
~]       # convert input to an integer
{        # loop 4 times (enough for a 5-elements input)
  {      # inject this block into the array
    .    # duplicate (l r r)
    2/   # determine surviving people (l r r%2)
    @+\  # add to the left (l+r/2 r)
    2%   # determine remaining people (l+r/2 r%2)
  }*
  ]      # make array again of the results
}4*
' '*     # format output

```

# Answer
> 8 votes
## GolfScript (25 chars)

```
~]-1%{\.1&\2/@+}*]-1%' '*

```

Online demo

Pretty straightforward solution: there's a more interesting approach which defines the output value for each island as a function of the input values, but I don't think it can be golfed nearly as far as actually following the redistribution algorithm described in the question.

# Answer
> 7 votes
## Javascript/ES6 (69)

Playing with bitwise operators :

* `x&=1` keeps the lowest bit (1 if odd, 0 if even)
* `x>>1` is division by 2 for integers

```
f=a=>{a=a.split(' ');for(i=5;--i;a[i]&=1)a[i-1]-=-(a[i]>>1);return a}

```

Version without ES6 :

```
function f(a){a=a.split(' ');for(i=5;--i;a[i]&=1)a[i-1]-=-(a[i]>>1);return a}

```

Examples :
`f("3 8 6 0 2")` returns `[8, 1, 0, 1, 0]`
`f("0 997 998 999 1000")` returns `[935, 0, 1, 1, 0]`

# Answer
> 6 votes
## Python - 96 Characters

First time golfing! Input from stdin.

```
n=map(int,raw_input().split())
x=4
while x:n[x-1]+=n[x]/2;n[x]%=2;x-=1
print' '.join(map(str,n))

```

# Answer
> 5 votes
# Ruby, ~~97~~ ~~90~~ ~~74~~ 72

Online version

Golfed it a bit further, not reversing the array anymore...

```
f=->i{i=i.split.map(&:to_i);(1..4).each{|n|i[-n-1]+=i[-n]/2;i[-n]%=2};i}

```

# Answer
> 5 votes
# J (26 characters)

Here is my solution in J: `((<.@-:@}.,0:)+{.,2|}.)^:_`

```
   islands1 =: 3 8 6 0 2
   islands2 =: 3 8 6 3 2
   ((<.@-:@}.,0:)+{.,2|}.)^:_ islands1
8 1 0 1 0
   ((<.@-:@}.,0:)+{.,2|}.)^:_ islands2
9 0 0 0 0

```

This general solution should work with any number of islands.

# Answer
> 4 votes
# C - 121 characters

Input is taken from stdin.

```
a[5];main(i){b(i=0,0);while(i++<5)printf("%i ",a[i-1]);}b(i,j){scanf("%i",&i);return j<5?i+=
b(i,j+1)/2,a[j]=j?i&1:i,i:0;}

```

# Answer
> 4 votes
# Python2 - 98 characters

Input from stdin.

```
s=[0]
for v in raw_input().split()[::-1]:s=[int(v)+s[0]/2,s[0]%2]+s[1:4]
print' '.join(map(str,s))

```

# Python3 - 79 characters

Input from stdin.

```
s=[0]
for v in input().split()[::-1]:s=[int(v)+s[0]//2,s[0]%2]+s[1:4]
print(*s)

```

# Answer
> 4 votes
Python 2, 85 80 bytes

```
b=1
for x in raw_input().split():b=2*b+int(x)
print b/16-2,' '.join(bin(b)[-4:])

```

X people starting on any island are equivalent to X\*2 people starting one island to the right. This code converts everyone in the starting configuration to their equivalent in far-right-islanders, then uses the binary representation of the result to determine how many people end up on each island.

EDIT: Shortened the code by initializing `b` to 1 instead of 0, allowing the use of `bin` instead of a format string.

# Answer
> 3 votes
# Python (101)

```
l=map(int,raw_input().split())
for i in range(4):l[3-i]+=l[4-i]/2;l[4-i]%=2
print' '.join(map(str,l))

```

We loop through the list from back to front and move the populations around according to the specification, then print the list. Here's a quick test:

```
>>> l=map(int,raw_input().split())
3 8 6 0 2
>>> for i in range(4):l[3-i]+=l[4-i]/2;l[4-i]%=2
...
>>> print' '.join(map(str,l))
8 1 0 1 0

```

# Answer
> 2 votes
# Mathematica 105

This should work with any number of islands.

```
f[w_,n_:1]:=
If[n==Length@w,w,
f[w~ReplacePart~{-n-> Mod[z=w[[-n]],2],-(n+1)->(w[[-(n+1)]]+ z~Quotient~2)},n+1]]

```

## Examples

5 islands

```
f[{3, 8, 6, 0, 2}]

```

> {8, 1, 0, 1, 0}

---

25 islands

```
f[{145, 144, 144, 59, 35, 129, 109, 99, 200, 24, 219, 96, 12, 121, 75,20, 153, 124, 131, 178, 228, 120, 63, 207, 228}]

```

> {270, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0}

# Answer
> 2 votes
# Java - ~~647~~ 533 but hoping for some brownie points for Java 8 Streams.

```
class I{int p;I e;I(int p,I e){this.p=p;this.e=e;}void x(){if(e!=null){int r=p&1;e.p+=(p-r)/2;p=r;}}public String toString(){return ""+p;}}Deque<I>B(String d){H<I>e=new H<>();return Arrays.stream(d.split(" ")).map(s->Integer.valueOf(s)).map(p->e.hold(new I(p,e.held()))).collect(Collectors.toCollection(LinkedList::new));}void x(Deque<I>is){is.descendingIterator().forEachRemaining((I i)->{i.x();});}void t(String s){Deque<I> a=B(s);x(a);System.out.println(a);}class H<T>{T h=null;H(){}T hold(T t){return (h=t);}T held(){return h;}}

```

The uncompressed form:

```
private static class Island {
  int population;
  final Island eastwardIsland;

  Island(int population, Island eastwardIsland) {
    this.population = population;
    this.eastwardIsland = eastwardIsland;
  }

  private void exodus() {
    if (eastwardIsland != null) {
      // How many remain.
      int remain = population & 1;
      // How many leave.
      int leave = population - remain;
      // Account for 50% death rate.
      int arrive = leave / 2;
      // Modify the eastward island population.
      eastwardIsland.population += arrive;
      // Change my population.
      population = remain;
    }
  }

  @Override
  public String toString() {
    return String.valueOf(population);
  }

}

private Deque<Island> buildIslands(String data) {
  // Holds the island to the east as we traverse.
  final Holder<Island> eastward = new Holder<>();
  // Build my list of islands - assumes order is retained.
  return Arrays.stream(data.split(" "))
          // Convert to int.
          .map(s -> Integer.valueOf(s))
          // Build the island in a chain.
          .map(p -> eastward.hold(new Island(p, eastward.held())))
          // Roll them into a linked list.
          .collect(Collectors.toCollection(LinkedList::new));
}

private void exodus(Deque<Island> islands) {
  // Walk backwards.
  islands.descendingIterator()
          // Perform all exodus.
          .forEachRemaining((Island i) -> {
            i.exodus();
          });
}

private void test(String data) {
  Deque<Island> archipelago = buildIslands(data);
  // Initiate the exodus.
  exodus(archipelago);
  // Print them.
  System.out.println(archipelago);
}

```

With an assist of:

```
// Mutable final.
private static class Holder<T> {
  private T held = null;

  public Holder() {
  }

  public Holder(T it) {
    held = it;
  }

  public T hold(T it) {
    return (held = it);
  }

  public T held() {
    return held;
  }

  @Override
  public String toString() {
    return held == null ? "null" : held.toString();
  }

}

```

Slightly concerned that @DavidCarraher's test:

```
145 144 144 59 35 129 109 99 200 24 219 96 12 121 7520 153 124 131 178 228 120 63 207 228

```

generates

```
270, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0

```

# Answer
> 2 votes
## Java - ~~196~~ 195

I told myself I wouldn't post it if I couldn't get it under 200... I honestly don't think I can get rid of anything else, it's pretty slim for Java.

```
class H{public static void main(String[]a){int l=a.length,p[]=new int[l],i=l;for(;i-->0;){p[i]=Integer.valueOf(a[i]);if(l-i>1){p[i]+=p[i+1]/2;p[i+1]%=2;}}for(;++i<l;System.out.print(p[i]+" "));}}

```

Line breaks:

```
class H{
    public static void main(String[]a){
        int l=a.length,p[]=new int[l],i=l;
        for(;i-->0;){
            p[i]=Integer.valueOf(a[i]);
            if(l-i>1){
                p[i]+=p[i+1]/2;
                p[i+1]%=2;
            }
        }
        for(;++i<l;System.out.print(p[i]+" "));
    }
}

```

**Sample input output:**

```
$ java H 3 8 6 0 2
8 1 0 1 0

$ java H 0 1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 0 1 0 0

$java H 235 897 158 693
809 1 0 1

```

# Answer
> 2 votes
## Java - 179 characters

**Compressed:**

```
class F{public static void main(String[] a){int l=0,x,s,i=a.length-1;String z="";for(;0<=i;i--){x=Integer.valueOf(a[i])+l;s=i>0?x%2:x;l=(x-x%2)/2;z=s+" "+z;}System.out.print(z);}}

```

**Normal:**

```
public class FloatingHorde {

    public static void main(String[] a) {
        int leave = 0;
        String outputStr = "";
        for (int i = a.length - 1; 0 <= i ; i--) {
            int x = Integer.valueOf(a[i]) + leave;
            int stays = i > 0 ? x % 2 : x;
            leave = (x - x % 2) / 2;
            outputStr = stays + " " + outputStr;
        }
        System.out.print(outputStr);
    }
}

```

**Sample output:**

```
$ java F 3 8 6 0 2
8 1 0 1 0

$ java F 7 6 5 4 3
11 1 1 1 1

```

# Answer
> 0 votes
## Emacs Lisp 144 chars

Not tiny, but it works

```
(lambda (d)
   (setq x d)(while(cdr x)
           (setcar(cdr x)(+(/(-(car x)(%(car x)2))2)(cadr x)))
           (setcar x (-(car x)(*(/(car x)2)2)))
       (pop x))
   (reverse d))

```

# Answer
> 0 votes
# awk - 44 Characters

```
{for(i=NF;i>1;){n=int($i/2);$i%=2;$--i+=n}}1

```

# Answer
> -2 votes
# Java - 116 Characters

For example `int[] i = {2, 33, 16, 5};` (I guess those don't add to the count, since each number can vary) would output `23 0 0 1`

```
for(int j = i.length-1; j > 0; j--) {
    while(i[j] > 1) {
        i[j] -= 2;
        i[j-1]++;
    }
}
for(int j = 0; j < i.length; j++) {
    System.out.print(i[j] + " ");
}

```

---
Tags: code-golf
---