title: Office Escape: Plan your way out!

text:
# Question
Title: Office Escape: Plan your way out!
It's the final sprint... and half your team is off ill. You're working late, just making your last commit for the day, looking forward to... why have the lights turned off? I don't remember the security guy coming around... oh no! I left my keys at home!

As the horror of the situation sinks in, you decide that *you are going to escape*.

## Task Summary

To effect your escape, you need a plan! However, you know that any plan has a chance of failing, and different plans require different amounts of effort.

Being hungry, tired, and an engineer, you decide to write a short program to determine the best way to escape the complex, balancing the concerns of probability of success and the effort it will require.

You make a map of the building:

```
#######################
#                =    #
!                =    !    <-- window
#          !     =    #        (freedom!)
#################=    #
#    #           =    #
#    #           =    #
#    #           =    #
# o  !   # #  !  =    #
##|  !  ## #  !  =    #
#######################

  ^  ^           ^
  me my door     ludicrously high shelves
     (locked)    (climbable)

```

To escape the office, you will have to move yourself off the map. Here you see there are 2 windows (`!`), either one would lead you to freedom, but only one of them accessible. We define 'off the map' as having your feet outside the bounds of the map

Cell types

```
  - empty, you can be here (i.e. the escapee can consume this cell)
# - solid (your desk, your in-tray), you can't be here, but you can stand on it
! - destructible, (co-worker's desk, door, window), you can't be here until you smash it first (turning it into an empty cell)
= - climbable, (fire ladder, filing cabinet, etc.), you can be here

```

The cells originally consumed by the escapee taken to be empty.

## Action Specifications

You have a number of possible actions at your disposable. These are defined by simple state transitions with some integer success probability. For example, for walking, you move the escapee one cell, which we represent with this transition:

Step

1 stp, 100%, mirror

```
 o.            o
 |.   -->      |
 #            #

```

The dots show cells that must be empty (or climbable, but not solid or destructible) either because we move into it or through it. The 100% means you have an 100% chance of not hurting yourself and ending your daring escape. All probabilities will be integer percentages between 1% and 100% inclusive. The first diagram shows the initial state (standing on something solid, standing next to some empty space). The second diagram shows the terminal state (moved into the empty space). There is no requirements for any unspecified cells (spaces, ) on the left (initial state) to be anything in particular. Unspecified cells (space, ) on the right (terminal state) should be the same as they were prior (e.g whatever was behind the escapee, or whatever I happen to be walking onto (be it empty space or otherwise). Note that all right-hand (terminal state) diagrams will only change cells from destructible to empty, no other changes can occur. "1 stp" means it costs 1 stp: we define the "stp" as the amount of energy required to take a step.

"mirror" means this action has two forms. The "right" action is shown, the "left" action is an exact mirror, for example:

```
.o
.|
 #

```

is the mirror (Left) form of

```
o.
|.
#

```

The right action is called " Right" (e.g. "Step Right") The left action is called " Left" (e.g. "Step Left")

In these diagrams, the escapee is show by

```
o
|

```

when standing (2 units tall) and

```
%

```

when crouching (1 unit tall). Cells that must be solid or destructible are indicated by a hash, `#`. Cells that must not be solid or destructible are indicated by a dot `.`. Cells that must be destructible are indicated by a bang `!`. A newly created empty space is shown by an underscore `_`. `x` is a reference point that doesn't move (it doesn't exist, no constraint on what that cell must be (like a space )).

Note: we ignore the issue of rapid deceleration when you hit the floor, and yes, in this game you can do totally epic jumps onto ladders)

## Step

1 stp, 100%, mirror

```
 o.         o
 |.  -->    |
x#        x#

```

## Climb off

1 stp, 100%, mirror

```
 =         =
 o.  -->    o
 |.         |
x=        x=

```

## Shuffle

3 stp, 100%, mirror

```
 %.         %
x#   -->  x#

```

## Clamber Up

10 stp, 95%, mirror

```
 o.         %
 |#  -->    #
x#        x#

```

## Drop

0 stp, 100%

```
 o
 |  -->   o
x.       x|

```

## Drop (Stand)

0 stp, 100%

```
 %        o
x.  -->  x|

```

## Climb Up

2 stp, 100%

```
 =        o
 o  -->   |
x|       x

```

## Crouch

2 stp, 100%

```
 o
 |  -->   %
x#       x#

```

## Stand

4 stp, 100%

```
 .        o
 %  -->   |
x#       x#

```

## Short Jump

4 stp, 95%, mirror

```
 o..          o
 |..  -->     |
x#         x#

```

## Long Jump

7 stp, 75%, mirror

```
 o...           o
 |...  -->      |
x#          x#

```

## High Jump

12 stp, 90%, mirror

```
 ..         o
 o.  -->    |
 |
x#        x#

```

## Put your back into it!

20 stp, 80%, mirror

```
 o!.         _o
 |!.  -->    _|
x#         x#

```

## Punch

8 stp, 90%, mirror

```
 o!        o_
 |   -->   |
x#        x#

```

## Kick

8 stp, 85%, mirror

```
 o         o
 |!  -->   |_
x#        x#

```

## Stamp

8 stp, 90%

```
 o        o
 |  -->   |
x!       x_

```

## Plans

A plan is a sequence of the actions defined above. For example:

```
Step Left
High Jump Left
Crouch
Shuffle Left
Shuffle Left
Stand
Long Jump Left
Put your back into it! Left
Step Left

```

Note the inclusion of the drops. The rules should be set up to stop you doing anything but dropping, but you still have to plan for it!

Any plan has a required effort, which is the sum of the efforts for each step. There is also a success probability, which is the product of the success probabilities of each action. Simple example:

```
Step Right:          1stp,  100%
Long Jump Right:     7stp,  75%
Step Right:          1stp,  100%
Stamp:               8stp,  90%
Drop:                0stp,  100%
Drop:                0stp,  100%
Drop:                0stp,  100%
Drop:                0stp,  100%
Step Left:           1stp,  100%
Step Left:           1stp,  100%
High Jump Left:      12stp, 90%

Effort = 1+7+1+8+1+1+12 = 31
Success Probability = 75%*90*90% = 60.75%

```

A 'worked example' for the map at the top of page can be found as a gist.

## Input

The input comes in two parts, an integer, and an array or string of characters.

The integer is your minimum acceptable (percent) probability of success. It is to be interpreted as a percentage, so 80 means your plan must succeed with probability no less than 80%.

A valid map is a rectangle that includes the standing escapee (minimum size of 1x2) and no unspecified symbols. All rows will be the same length. You may accept input as a 1-dimensional delimitated string (delimiter must be a single consistent character, or one of CRLF and LFCR pair), as a similar 1-dimensional array, or a 2-dimensional array. If your chosen input format does not indicate the width or height of the map in some way, you may accept additional arguments for these (you must clearly state this in your answer). You may mix command line arguments and standard input if it suits you (e.g. map from stdin, minimum success probability from argv). The following are example valid and invalid maps.

Valid:

```
o
|

```

Valid:

```
  #     #
  !   o #
  !   | #
#########

```

Invalid (no escapee):

```
  #     #
  !     #
  !     #
#########

```

Invalid (escapee always starts standing):

```
  #     #
  !     #
  !   % #
#########

```

Invalid (invalid symbol):

```
  #     #
  !  ~  #
  !     #
#########

```

Invalid (not a rectangle/different length rows):

```
  #     #
  !   o #
  !   | #
#########

```

You may assume your input is valid (I don't care what your program does if it is handed invalid input).

## Output

Output is text (ASCII). May be returned as a string, or printed to standard output. The plan must be delimitated by a LF, CRLF, or LFCR. Similarly, there must be another LF, CRLF, or LFCR after the Required Effort. A trailing line break is optional.

You must output an optimal plan along with the effort it requires, or "There is no hope!" if no such plan exists. You do not need to output the probability of success. This text may or may not have trailing line break.

An optimal plan is defined as a plan (see above) requiring the minimum effort with at least the given probability of success. Note that you probability calculations must be exact, you may not assume that floating point is good enough (This is why I don't expect you to output them). I will try to design test cases to fairly test this (if you pass them and don't make any daft assumptions then you may consider your submission valid).

Format:

```
Required Effort: <effort>
<plan>

```

For example, for the input

```
50
  #     #
  !   o #
  !   | #
#########

```

An appropriate output would be:

```
Required Effort: 23
Step Left
Step Left
Step Left
Kick Left
Punch Left
Step Left
Step Left
Step Left
Step Left

```

The probability of success here is 76.5%.

For the same map, but a minimum probability of success of 80%, you would have to "Put your back into it", which would require more effort but fulfil the success probability criteria. If the minimum probability of success were greater than 80%, you'd need to think a bit harder (either punch or kick through part of the door and shuffle out). If the minimum probability of success were 100%, you'd have to print out "There is no hope!"

### Examples

*It is possible that there are more than one valid plans for an input, you're output doesn't need to be these exactly, but it must have the correct required effort, and be a valid plan. You can use the verifier to check your solutions (see below)*

Input:

```
100
o
|

```

Output:

```
Required Effort: 0
Drop

```

Input:

```
5
# =      #
# =      !
# = !  ! !
# =#######
# =      #
# =   o  #
# = ! |  #
##########

```

Output:

```
Required Effort: 57
Step Left
Kick Left
Step Left
Step Left
Step Left
Climb Up
Climb Up
Climb Up
Climb Up
Climb off Right
High Jump Right
Long Jump Right
Step Right
Drop
Kick Right
Crouch
Shuffle Right
Shuffle Right

```

Input:

```
60
#########
# ! #   #
! ! ! o #
! # ! | #
#########

```

Output:

```
Required Effort: 58
Step Left
Kick Left
Crouch
Shuffle Left
Shuffle Left
Stand
Punch Left
Clamber Up Left
Shuffle Left
Drop (Stand)
Kick Left
Crouch
Shuffle Left
Shuffle Left

```

For the same map, but 80%, the output should be:

```
There is no hope!

```

For the same map, but 50%, the Required effort becomes 56 with a different plan)

Input:

```
50
#######################
#          #     =    #
!          #     =    !
#          #     =    #
######  #####!## =### #
#=   ##       #  =    #
#=#############  =    #
#=               =    #
#= o             =    #
#!!|             =    #
#######################

```

Output:

```
Required Effort: 121
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Climb Up
Climb Up
Climb Up
Climb Up
Climb Up
Climb Up
Climb off Right
Long Jump Left
Step Left
Step Left
Stamp
Drop
Drop
Crouch
Shuffle Left
Shuffle Left
Shuffle Left
Shuffle Left
Shuffle Left
Shuffle Left
Stand
Clamber Up Left
Stand
Clamber Up Left
Stand
Step Left
Step Left
Step Left
Step Left
Punch Left
Clamber Up Left
Shuffle Left

```

Input:

```
66
######
#  ###
#o ! !
#| ! !
### ##
######

```

Output:

```
Required Effort: 37
Step Right
Put your back into it! Right
Kick Right
Crouch
Shuffle Right
Shuffle Right

```

Input:

*This one is designed to check a number of false assumptions one may fall victim to, and consequently may look a bit odd*

```
30
###################
# ## # # #   #  = #
! ## #   #   #  = #
#      #   #    = #
##  ############= #
# ## #         #= #
# =  #         #= #
! =  #         #= #
# =  #         #= #
#o=  !          ==#
#|=  !           =#
#!= # ==########==#
#   #    !   !!  =#
#   #    !!  !  = #
#   # !!!!#########
#   # #           #
#   # #           #
###################

```

Output with chance of success constraint 30:

```
Required Effort: 199
Long Jump Right
Put your back into it! Right
<snip>

```

Output with chance of success constraint 32:

```
Required Effort: 200
Long Jump Right
Punch Right
<snip>

```

Using the map at the top as an input, with probability of success constraint 1%, you should get a Required Effort of 116 (chance of success ~32%, this took about 20seconds to run in my test program).

## Victory Criteria

This is code-golf, may the shortest code win.

To be eligible, your function or program must work and be able to solve each of the above testcases in under 30minutes on a reasonable machine. My solver does them each in under 30seconds. If the test script (below) runs in under 30minutes, you're certainly good to go.

## Example Solver, Verifier, Test Script, and TestCases (with solutions)

C# code for a solver, and solution verifier, is available here as a gist. The gist also contains `file.txt`, which is a machine readable (enough) form of the actions described above, and is required for the program to run. Any discrepancy between that file and spec is not intentional.

The gist also contains a number of test cases (including all the examples above), and a PowerShell script to automatically run a submission against them. If the script tells you that a particular test has failed, you can run `OfficeEscapeSolver.exe testcase<n>.txt outputFromYourProgram.txt` to see more details. Example solutions for these test cases are in another Gist.

All the code is a complete mess (though ungolfed), but you shouldn't need to stray far from the `static void Main(...)` to change the amount of output (feel free to use this information, I've provided it for your benefit!).

Passing a test-case does not necessarily mean that your output is well formed, as the script and verifier are very generous. Your output must match the specification above for your submission to be valid.

If you think you've found a bug with the solver or testscript, an error in `file.txt`, or a dodgy testcase, then please comment on this post or otherwise ping me on SE Chat; I probably won't notice any other attempt to communicate.

I won't provide the test script in Bash or Batch, because I don't know them, but I'm happy to include a translation and will write a C# version if people want one.

# Post Amble

Got questions? Don't delay, ask them today!

This task is meant to *require effort*, to give serious golfers something to sink their teeth into.

My thanks to ais523 for his feedback on Input/Output.

I can provide more testcases in the gist file if people want more (don't want this post to become any longer), or want to provide some of their own.

# Answer
---

# Perl 5, ~~1425~~ ~~1464~~ ~~1481~~ ~~1469~~ ~~1485~~ 1438 bytes

That was a fun challenge! And, shockingly, it looks like I have the shortest code so far at a little under 1.5kB! :)

Pretty sure I finally got this working. The delimiter used is `:`~~, and there is extra padding of two rows on top and one column on either side~~. So for your input of:

```
60
#########
# ! #   #
! ! ! o #
! # ! | #
#########

```

my program would take: (NB: there must be a colon at the end, but not at the beginning!)

```
60
#########:# ! #   #:! ! ! o #:! # ! | #:#########:

```

I use regexes to translate from one map to another and solve by brute force. However, I don't add maps to the list if that map has already been reached with less effort and greater or equal probability. Maps are removed from the list once all possible movements from that point have been exhausted. The program ends successfully when it matches a regex that shows I have reached the side or the bottom and ends with "There is no hope!" when the list of maps is exhausted.

Unfortunately, there was a great deal of efficiency traded away to take off a few bytes, so the golfed version is rather slow ;) Perl seems to find the evals in particular to be quite painful.

Without further adieu,

```
chop($P=<>,$_=<>);s/:/ : /g;$w++until/:.{$w}:/;$z=$"x$w;$_="(.{".$w--."})"for($c,$h,$i,$j);$_="$z:$z: $_$z";$n="[ =]";$d="([!#])";@s=split/,/,'Drop,Drop (Stand),Stepx,Climb offx,Shufflex,Clamber Upx,Put your back into it!x,Punchx,Kickx,Short Jumpx,Long Jumpx,High Jumpx,Crouch,Stand,Climb Up,Stamp';@c=split/,/,"o$c\\|$c$n/ \$1o\$2|,%$c$n/o\$1|,o$n$h\\|$n$h${d}/ o\$1 |\$2\$3,=${c}o$n$h\\|$n$h=/=\$1=o\$2=|\$3=,%$n$h$d/ %\$1\$2,o$n$h\\|${d}$h${d}/ %".'$1 $2$3$4,'."o!$n$i\\|!$n$i${d}/  o\$1  |\$2\$3,o!$h\\|$c$d/o \$1|\$2\$3,\\|!$h$d/| \$1\$2,o$n$n$i\\|$n$n$i${d}/  o\$1  |\$2\$3,o$n$n$n$j\\|$n$n$n$j${d}/   o\$1   |\$2\$3,$n$n${h}o$n$h\\|$c$d/ o".'$1 |$2 $3$4,'."o$c\\|$c${d}/ \$1%\$2\$3,$n$c%$c${d}/o\$1|\$2\$3,=${c}o$c\\|/o\$1|\$2=,\\|$c!/|\$1 ";eval"*$_=sub{\$Q=\"$s[$_]\";s/$c[$_]/}"for(0..15);sub M{$_=join":",map{join'',reverse split//}split/:/};push@M,[$_,0,100,$P];$B{$_}=100;@E=(0,0,1,1,3,10,20,8,8,4,7,12,2,4,2,8);@P=map{100-$_}(0,0,0,0,0,5,20,10,15,5,25,10,0,0,0,10);$z='$N=[$_,$G+0,$t,$t[3]*100,"$t[4]$Q\n"];$N->[4]=~s/x/';do{sub A{@N=@$N;if($N[2]/$N[3]>$B{$N[0]}){push@M,$N;$B{$N[0]}=$N[2]/$N[3]}};die"There is no hope!\n"if(!(@M=grep$G-$_->[1]<21,@M));$e=-1;while(++$e<@M){@t=@{$M[$e]};$m=$_=$t[0];die"Required Effort: $t[1]\n$t[4]"if(/([|%]:|:[|%])/||/[|%][^:]*$/||/^$c:[^:]*[%|]/);for$x(0..15){$_=$m;$t=$t[2]*$P[$x];if($G==$E[$x]+$t[1]and$t>=$t[3]*100){&$x;eval"$z Right/";A;$_=$m;M;&$x;M;eval"$z Left/";A;}}}}

```

For the sake of sanity, here's the same thing with newlines and a few comments:

```
chop($P=<>,$_=<>); #Take input
s/:/ : /g; #Pad columns on either side so escapee can leave that way
$w++until/:.{$w}:/; #Find width
$z=$"x$w;#Setup a blank line for use in padding later
$_="(.{".$w--."})"for($c,$h,$i,$j); #Set up some generic capturing regexes for reuse
$_="$z:$z: $_$z"; #Pad the top and bottom so the escapee can leave those ways
$n="[ =]"; #Regex for nonsolid block
$d="([!#])"; #Regex for solid block
@s=split/,/,'Drop,Drop (Stand),Stepx,Climb offx,Shufflex,Clamber Upx,Put your back into it!x,Punchx,Kickx,Short Jumpx,Long Jumpx,High Jumpx,Crouch,Stand,Climb Up,Stamp'; #Movement names
@c=split/,/,"o$c\\|$c$n/ \$1o\$2|,%$c$n/o\$1|,o$n$h\\|$n$h${d}/ o\$1 |\$2\$3,=${c}o$n$h\\|$n$h=/=\$1=o\$2=|\$3=,%$n$h$d/ %\$1\$2,o$n$h\\|${d}$h${d}/ %".'$1 $2$3$4,'."o!$n$i\\|!$n$i${d}/  o\$1  |\$2\$3,o!$h\\|$c$d/o \$1|\$2\$3,\\|!$h$d/| \$1\$2,o$n$n$i\\|$n$n$i${d}/  o\$1  |\$2\$3,o$n$n$n$j\\|$n$n$n$j${d}/   o\$1   |\$2\$3,$n$n${h}o$n$h\\|$c$d/ o".'$1 |$2 $3$4,'."o$c\\|$c${d}/ \$1%\$2\$3,$n$c%$c${d}/o\$1|\$2\$3,=${c}o$c\\|/o\$1|\$2=,\\|$c!/|\$1 ";#Movement regexes
eval"*$_=sub{\$Q=\"$s[$_]\";s/$c[$_]/}"for(0..15); #Setup methods to apply regexes. Name of these methods are 0,1,2,3, etc, so we can easily call them in a loop
sub M{$_=join":",map{join'',reverse split//}split/:/}; #Method to mirror the map. All the regexes are right-moving, so the mirror effects are achieved by M;&$x;M
push@M,[$_,0,100,$P]; #Array for initial map position. Encodes: [Map,Effort value,Probability value 1,Probability value 2,Movements(initially undef)]. Two integers are used for the probability to avoid floating point (although after enough steps they overflow and are automatically converted to f.p.)
$B{$_}=100; #Hash map to hold best probability of reaching a map. A new map is never added if it requires at least as much effort and doesn't give a better probability.
@E=(0,0,1,1,3,10,20,8,8,4,7,12,2,4,2,8); #Effort values
@P=map{100-$_}(0,0,0,0,0,5,20,10,15,5,25,10,0,0,0,10); #Probability values
$z='$N=[$_,$G+0,$t,$t[3]*100,"$t[4]$Q\n"];$N->[4]=~s/x/'; #Setup map values
do{ #Loop over all efforts. Do-while loop starts at undef, which is converted to zero automatically when used in a numeric context
    sub A{@N=@$N;if($N[2]/$N[3]>$B{$N[0]}){push@M,$N;$B{$N[0]}=$N[2]/$N[3]}}; #Method to add a map to list.
    die"There is no hope!\n"if(!(@M=grep$G-$_->[1]<21,@M)); #Pares away maps that no longer can produce new maps, and prints "There is no hope!" to stderr if there are no maps left.
    $e=-1;
    while(++$e<@M){ #Loop over all maps. Note that this loops over even maps that are created during the loop
        @t=@{$M[$e]}; #Dereference info about each map
        $m=$_=$t[0]; $Setup map variables
        die"Required Effort: $t[1]\n$t[4]"if(/([|%]:|:[|%])/||/[|%][^:]*$/||/^$c:[^:]*[%|]/); #Checks if escaped, and gives message if so.
        for$x(0..15){
            $_=$m; #Put map into $_
            $t=$t[2]*$P[$x]; #Probability calculation
            if($G==$E[$x]+$t[1]and$t>=$t[3]*100){ #If effort values are right and probability is over threshold
                &$x; #Run regex
                eval"$z Right/"; #Set up map info
                A; #Add map to list @M (only if probability works out right)
                $_=$m;
                M;&$x;M; #Same thing, but mirrored now (generates movement left)
                eval"$z Left/";
                A;
            }
        }
    }
}while(++$G)

```

I can already see a couple places to pare away a few more bytes, but I don't want to go through all the testing again yet. Later! :)

Edit: Added some padding below as well to fit your output more exactly when escaping through the floor. Removed some of the evals, so the code might run faster now, too!

Edit: Wasn't handling ladders and drops quite right. Still doesn't handle ladders quite right... Trying to fix that now.
> 2 votes

# Answer
# C#, ~~1814~~ ~~1481~~ 1395 bytes

*What a slog!! I'm really rather pleased with this now!*

```
using C=System.Console;using System.Linq;class S{string M,N="";int x,y,E,c;decimal P=1;static void Main(){int W=0,H=0,x,i,j,k,X,Y,f,m,P=int.Parse(C.ReadLine());string l,M="",B,R="There is no hope!";for(;(l=C.ReadLine())!=null;H++,M+=l)W=l.Length;x=M.IndexOf("|");var D=new[]{new S{M=M,x=x%W,y=x/W}}.ToList();for(var N=D.ToDictionary(s=>R,s=>D);D.Count>0;D.Sort((z,w)=>z.E-w.E)){S s=D[f=0];D.Remove(s);var n=N[l=s.x+s.M+s.y+s.c]=N.ContainsKey(l)?N[l]:new S[0].ToList();if(n.All(o=>o.P<s.P|o.E>s.E)){n.Add(s);X=s.x;Y=s.y;if((X|Y|-X/W-Y/H)<0){R="Required Effort: "+s.E+s.N;break;}for(var A="0110d,Step,*** * #*,0110d,Climb off,=** * =*,3310d,Shuffle,***** #*,2:1/_,Clamber Up,*** *##*,0420_,Short Jump,****  *  #**,0730K,Long Jump,*****   *   #***,0<1/Z,High Jump,  * **#*,0D20P,Put your back into it!,****! *! #**,0800Z,Punch,***!**#*,0800U,Kick,*****!#*,0001d,Drop,*** ,1001d,Drop (Stand),*** ,2200d,Crouch,***#,1400d,Stand,* *#,020/d,Climb Up,=***,0800Z,Stamp,***!".Split(',');f<26;){l=A[k=f*3%48];B=A[++k]+(f>15?" Right":f>9?"":" Left");M=A[++k];m=f++/16*2-1;var Q=s.M.ToArray();var K=s.P*l[4]>=P&s.c==l[k=0]%2;for(j=Y-3;j++<=Y;)for(i=X;i!=X+m*M.Length/4;i+=m)if((K&="==  *!!##*!*=*|*| o*o ".Contains(""+((i|j)>=0&j<H&i<W?Q[x=j*W+i]:' ')+M[k]))&M[k++]==33)Q[x]=' ';if(K)D.Add(new S{M=new string(Q),N=s.N+"\n"+B,x=X+l[2]%48*m,y=Y+l[3]-48,c=l[0]/50,E=s.E+l[1]-48,P=s.P*l[4]/100});}}}C.Write(R);}}

```

Try It Online

Complete program, takes input to STDIN, output's to STDOUT. Essentially a re-write of my original solver, using a simple and inefficiently implemented BFS to find the optimal path. It's reasonably fast, can't be much slower than my other implementation (I've not really timed it though), certainly runs within the time limit. Much of the cost is the Action table, which is encoded as comma separate values which record the name, 'match/smash' map, and other properties of each available action.

It starts by reading in the minimum probability of success and the map. Then it locates the escapee, removes him from the map, and creates a 'search state' containing this information. Then, it performs the BFS, which repeatedly looks at the next due state with the least effort (ensuring it finds an optimal solution). Before expanding the node, it compares it's effort and probability of success to previous nodes with the same map and escapee location, and rejects itself if a better route has been found to this state already. If it survives this, it adds itself to the 'seen' table so it can reject state later on. This is all for performance, and without it the branching factor would be huge. Then it checks if the escapee is off the map. If it is, then it wins! It back-tracks the state (each prior state is recorded with each state) and builds the plan (in reverse) before exiting the BFS loop. Otherwise, it tries to apply every action, and adds any that can be applied to the `due` queue, before sorthing this queue so that we get the least effort state next iteration.

Formatted and commented code:

```
using C=System.Console;
using System.Linq;

// ascii
//   32
// ! 33
// = 61
// . 46
// * 42
// # 35
// | 124
// 0 48

class S // SearchState
{
    string M, // map
        N=""; // plan
    int x, // pos x
        y, // pos y
        E, // effort
        c; // crouching?
    decimal P=1; // chance (Probability)

    static void Main()
    {
        int W=0, // map width
            H=0, // map height
            x, // various temps
            i, // local x
            j, // local y
            k, // position in match/smash map
            X, // s.x
            Y, // s.y

            // action loop
            f, // T idx
            m, // A idx, action mirror (direction)

            P=int.Parse(C.ReadLine()); // probability of success constraint

        string l, // line, Act 'block' params, map hash, match pairs; all sorts!
            M="", // initial map
            B, // name of action
            R="There is no hope!"; // result string

        // read map
        for(;(l=C.ReadLine())!=null; // while there is input to read
            H++,M+=l) // increment height, and append to M
            W=l.Length; // record width

        // detect the escapee
        x=M.IndexOf("|");

        // create first state, and add it to Due list
        var D=new[]{new S{M=M,x=x%W,y=x/W}}.ToList();

        // 'seen' table, stores all the states we've been in which looked similar
        for(var N=D.ToDictionary(s=>R,s=>D); // these values are meaningless (and necessarily can't interfere), we just use it to save having to spec the type
            D.Count>0; // keep going until we run out of states to expand (-> no escape)
            D.Sort((z,w)=>z.E-w.E)) // enforce Breadth First Search
        {
            // get next State to expand, and remove it from Due
            S s=D[f=0];
            D.Remove(s);

            // retrieve or create seen list
            var n=N[l=s.x+s.M+s.y+s.c]= // store it, and cache it, l is 'hash', containing map and escapee state
                N.ContainsKey(l)? // already got a seen list for ths map?
                N[l]: // then use it!
                new S[0].ToList(); // otherwise create a new (empty) one

            // perf: only proceed if we havn't seen this map with better Effort and Chance yet
            if(n.All(o=>o.P<s.P|o.E>s.E))
            {
                // record that we have been seen
                n.Add(s);
                X=s.x;
                Y=s.y;

                if((X|Y|-X/W-Y/H)<0) // check if we our outside the bounds - this took 2.5hour to write. 1 byte.
                { // quit if both are positive or both are negative
                    // freedom
                    R="Required Effort: "+s.E+s.N;

                    // finished
                    break;
                }

                // [Crouch,Effort,dx,dy,Probability],Name,MatchSmash (first 10 are mirrors)
                // 0110d,Step,*** * #*,
                // 0110d,Climb off,=** * =*,
                // 3310d,Shuffle,***** #*,
                // 2:1/_,Clamber Up,*** *##*,
                // 0420_,Short Jump,****  *  #**,
                // 0730K,Long Jump,*****   *   #***,
                // 0<1/Z,High Jump,  * **#*,
                // 0D20P,Put your back into it!,****! *! #**,
                // 0800Z,Punch,***!**#*,
                // 0800U,Kick,*****!#*,
                // 0001d,Drop,*** ,
                // 1001d,Drop (Stand),*** ,
                // 2200d,Crouch,***#,
                // 1400d,Stand,* *#,
                // 020/d,Climb Up,=***,
                // 0800Z,Stamp,***!

                // attempt to expand this node with every action
                for(var A="0110d,Step,*** * #*,0110d,Climb off,=** * =*,3310d,Shuffle,***** #*,2:1/_,Clamber Up,*** *##*,0420_,Short Jump,****  *  #**,0730K,Long Jump,*****   *   #***,0<1/Z,High Jump,  * **#*,0D20P,Put your back into it!,****! *! #**,0800Z,Punch,***!**#*,0800U,Kick,*****!#*,0001d,Drop,*** ,1001d,Drop (Stand),*** ,2200d,Crouch,***#,1400d,Stand,* *#,020/d,Climb Up,=***,0800Z,Stamp,***!".Split(','); // Act string
                    f<26;) // read A into T // (cycle over first 10 twice, making them mirrors)  (very convieniently, 3*16==48=='0'==x!)
                {
                    // 'parse' next action
                    l=A[k=f*3%48]; // [Effort,Crouch,dx,dy,Probability]
                    B=A[++k]+(f>15?" Right":f>9?"":" Left"); // action name
                    M=A[++k]; // Match and Smash table (4x?, escapee at 0,2, #: solid, !: smashable (and is smashed), .: empty,  : don't care, =: climable)
                    //c=l[1]-48; // crouching transition (0: standing -> standing, 1: crouching -> standing, 2: standing -> crouching, 3: crouching -> crouching)
                    m=f++/16*2-1;

                    // this will be the new map
                    var Q=s.M.ToArray();

                    // K is whether we are allowed to apply this action
                    var K=s.P*l[4]>=P& // within chance limit
                        s.c==l[k=0]%2; // crouching matches

                    // compare the map to the Match/Smash map, to make sure we can apply this transform (and smash any ! we meet)
                    for(j=Y-3;j++<=Y;) // for the 4 rows
                        for(i=X;i!=X+m*M.Length/4;i+=m) // for each column (a.M has height 4, but variable width)
                            if((K&= // K still true?
                                "==  *!!##*!*=*|*| o*o ".Contains(""+ // check for an allowed pairing (cache pairing in M) (this includes the escapee, much cheaper to do this than remove him)
                                    ((i|j)>=0&j<H&i<W?Q[x=j*W+i]:' ') // we are within bounds and match, we are out of bounds (empty)
                                    +M[k])) // char from MatchSmash map
                                &M[k++]==33) // if it is destructible ('!' == 33)
                                Q[x]=' '; // then blank it out (x is necessarily set by the cell check)

                    if(K) // if K holds
                        D.Add(new S{M=new string(Q),N=s.N+"\n"+B, // assemble plan as we go (this will chew up memory, but none of the problems are big enough for it to matter)
                            x=X+l[2]%48*m,y=Y+l[3]-48,c=l[0]/50,E=s.E+l[1]-48,P=s.P*l[4]/100}); // add the resulting state to Due
                }
            }
        }

        C.Write(R);
    }
}

```
> 2 votes

---
Tags: code-golf, path-finding
---


title: Determine the busiest time

text:
# Question
Title: Determine the busiest time
This challenge was greatly inspired by this Stack Overflow post.

# Challenge

Given a bunch of clients in terms of when they enter a room and when they exit it, determine the period(s) of time when the room has a maximum number of people. The time resolution should be to the minute.

For example, if there are three clients `8 - 10`, `9 - 11`, `10 - 12`, then the correct answer would be `9 - 11`; during this time period, there are two clients in the room, which is the largest possible.

# Input

Input will be a list of pairs in some form. That can be either a list of 2-tuples, an even-length list with elements interleaved, etc, any reasonable input format. The times can be given in any reasonable format, in either 12- or 24- hour time. You may also input time as the number of minutes past midnight.

# Output

Output should be a list of pairs in some form, but the output is stricter. The output cannot be a flat list, it must be a list of 2-tuples or a list of lists, etc. The times can be output in any reasonable format, in either 12- or 24- hour time. You may also output time as the number of minutes past midnight.

# Examples

```
input
output

INPUT
08:00 - 10:00
09:00 - 11:00
10:00 - 12:00
OUTPUT
09:00 - 11:00

INPUT
08:20 - 09:20
09:00 - 09:10
08:00 - 09:30
08:50 - 10:40
OUTPUT
09:00 - 09:10

INPUT
08:00 - 10:00
09:00 - 10:00
09:30 - 11:00
OUTPUT
09:30 - 10:00 # The output is not always in the input list

INPUT
00:00 - 02:00
01:00 - 03:00
04:00 - 06:00
05:00 - 07:00
OUTPUT # This is the expected output for when there are multiple time ranges with the same "business".
01:00 - 02:00
05:00 - 06:00

```

You may assume that the second time in a pair will always be after the first time. Time ranges will not run over midnight.

# Answer
# Brachylog, 25 bytes

```
⟦₂ᵐkᵐcoḅlᵒlᵍthᵐ~c{~k~⟦₂}ᵐ

```

Try it online!

There's an obvious structure to this answer, which becomes even more obvious if you write it like this:

```
{⟦₂k}ᵐc oḅ lᵒlᵍ thᵐ ~c{~k~⟦₂}ᵐ

```

Unfortunately, Brachylog's evaluation order makes it so that the program goes into an infinite loop if you try to take advantage of the structure in question. Still, it's certainly possible to imagine a Brachylog-like language in which this is much shorter.
> 4 votes

# Answer
# Jelly, ~~22~~ ~~21~~ 20 bytes

```
r/€Ṗ€F©®ċ$ÐṀQœ^‘$Ṣs2

```

Try it online!
> 3 votes

# Answer
# Brachylog, 58 bytes

```
⟦₂ᵐkᵐcoḅBlᵐ⌉;B↔z{hl~t?}ˢhᵐhᵐ{∋+₁.¬∈?∧|∋.-₁¬∈?∧}ᶠo~c.{l2}ᵐ∧

```

Try it online!

This has to be the longest Brachylog answer ever...
> 1 votes

# Answer
# Pyth, ~~33~~ 24 bytes

```
JsrMQcSs-M_BhMBS{.M/JZJ2

```

Try it online!
> 0 votes

# Answer
# Mathematica, 104 bytes

```
Reduce[#==#~MaxValue~x,x]&@PiecewiseExpand@Tr[Piecewise@{{1,#<=x<#2}}&@@@#]/.{Or->List,a_<=x<b_->{a,b}}&

```

Of course, this assumes that several high-power Mathematica built-ins are correct...
> 0 votes

---
Tags: code-golf, date
---


title: Venn Diagram Cells

text:
# Question
Title: Venn Diagram Cells
Given multiple sets, e.g. `s1={2,3,7}`, `s2={1,2,4,7,8}` and `s3={4,7}`, a Venn diagram visualizes each set by a closed curve and set elements which are either inside or outside the curve's perimeter, depending on whether they are element of the set or not. Because all set elements appear only once in the Venn digram, the curves representing each set need to overlap if an element is present in more than one set. We call each such overlapping a **cell** of the Venn diagram.

This explanation might be a bit confusing, so let's have a look at an example.

### Example

A Venn diagram for sets `s1`, `s2` and `s3` could look like this:

The cells of this Venn diagram are (read from top to bottom, left to right) `{1,8}`, `{2}`, `{7}`, `{4}`, `{3}`, `{}` and `{}`.

In practice, one commonly encounters only Venn diagrams of two or three sets, because the representation of Venn diagrams of four or more sets is not very clear. However they do exist, e.g. for six sets:
CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=1472309

### The Task

Given a non-empty set of sets of positive integers in any reasonable representation, return the set of cells of the input sets' Venn diagram. Specifically, **no** graphical representation is needed.

* You may write a full program or a function.
* You may return as many empty sets as there are empty cells (i.e. a *list* of all cells) instead of just one empty set (i.e. the *set* of cells).
* Some reasonable ways of input for the above example include but are not limited to `{{2,3,7},{1,2,4,7,8},{4,7}}`, `[[2,3,7],[1,2,4,7,8],[4,7]]`, `"2,3,7;1,2,4,7,8;4,7"` or `"2 3 7\n1 2 4 7 8\n4 7"`. If in doubt whether your chosen input format is acceptable, feel free to ask in a comment.
* Your output format should match your input format, if possible. Note that this rule requires your format to be able to unambiguously display empty sets.
* This is , so try to use as few bytes as possible in the language of your choice. In order to encourage competition per language instead of between languages, I won't accept an answer.

### Test Cases

Here are some inputs along with possible outputs:

```
input -> output
{{2,3,7},{1,2,4,7,8},{4,7}} -> {{1,8},{2},{7},{4},{3},{}} (or {{1,8},{2},{7},{4},{3},{},{}})
{{1,2,3},{4,5,6},{7,8,9}} -> {{1,2,3},{4,5,6},{7,8,9},{}}
{{}} -> {{}}
{{1,2,3},{1,2}} -> {{1,2},{3},{}}
{{4,3,8},{1,2,9,3},{14,7,8,5},{6,11,3,8},{10},{9,4,3,7,10}} -> {{6,11},{10},{4},{3},{8},{5,14},{1,2},{9},{7},{}}
{{2,3,4,7},{},{1,3,7,5,6},{2,3,7,5},{7,2,4,3,6},{1,4,5}} -> {{},{4},{2},{7,3},{1},{6},{5}}
{{1,2,3,4},{1,2,5,6},{1,3,5,7}} -> {{4},{3},{2},{1},{6},{5},{7}}

```

# Answer
# Haskell, 71 bytes

An anonymous function taking a list of lists of integers and returning a similar list.

Use as `(foldr(\x r->(x\\(id=<<r)):([intersect x,(\\x)]<*>r))[])[[1,2,3],[1,2]]`.

```
import Data.List
foldr(\x r->(x\\(id=<<r)):([intersect x,(\\x)]<*>r))[]

```

Try it online!

# How it works

* Uses the set-like operations `\\` (difference) and `intersect` from `Data.List`.
* Folds the list of "sets" (represented as lists) into a list of cells, starting with the empty list `[]`.
* `x` is the current set to be added to the diagram, and `r` is the list of cells already constructed.
    + `x\\(id=<<r)` is the subset of elements of `x` that are not in any of the already constructed cells.
    + `[intersect x,(\\x)]<*>r` splits up each cell in `r` according to whether its elements are in `x` or not.
* Most definitely does *not* attempt to merge empty cells, so there are quite a bit of those in the output.
> 8 votes

# Answer
# Perl 5, 79 bytes

```
sub{for$.(0..@_){$x{$_}+=2**$.for@{$_[$.]}};push@{$h{$x{$_}}},$_ for keys%x;%h}

```

Takes input as a list of anonymous arrays like (\[2,3,7\],\[1,2,4,7,8\],\[4,7\]). Outputs a hash where the keys are labels and the values are anonymous arrays corresponding to the output sets.

As part of a full program:

```
*x=
sub{for$.(0..@_){$x{$_}+=2**$.for@{$_[$.]}};push@{$h{$x{$_}}},$_ for keys%x;%h};
%x=x([2,3,7],[1,2,4,7,8],[4,7]);
print"Set $_:@{$x{$_}}\n"for keys%x;

```

Explanation:

Gives each set an integer as a label, `$.`. Creates a hash that stores an integer for each unique element `$_`. Adds `2**$.` for each set that `$_` appears in, effectively making a binary map showing what sets each element appears in. Finally, makes an anonymous array for each cell of the Venn diagram and pushes the elements appearing in the corresponding sets to the array. So each element of each array exists in the same sets and thus the same cell of the Venn diagram.
> 4 votes

# Answer
# Jelly, ~~14~~ 17 bytes

```
FṀ‘³iþ¬Ḅµ;ṀḶ$ĠṖṖ€

```

Try it online!

Function submission (because the format Jelly prints lists in by default doesn't round-trip – it can't read its own output format – but a function inputs and outputs in the same format). The TIO link contains a footer that runs the function and prints its output in the same format that input is parsed.

## Explanation

```
FṀ‘³iþ¬Ḅµ;ṀḶ$ĠṖṖ€
FṀ‘               Find the largest number that appears in any of the input sets, + 1
   ³ þ            For each number from 1 to that number, and each of the input sets
    i ¬             find whether the number is missing from the set
       Ḅ          Convert the list of missing sets into a single number using binary
         ;        Append
        µ ṀḶ$     all numbers from 0 to the maximum value minus 1
             Ġ    Group indexes by values
              ṖṖ€ Delete the last group and last element of other groups

```

The requirement that we output at least one empty set if not all the Venn diagram sections are used manages to take up over half the program here (it's responsible for the  that makes sure we have at least one group for non-matching elements, allowing us to keep track of how many sets there were originally, plus the last nine bytes of the source code except for the `Ġ`). The basic way in which we implement it is to ensure that all the 2^*n* Venn diagram subsets have at least one entry, by adding a dummy entry that will fill the "in no sets" section and (later) a dummy entry to each other section, then `Ġ` will output a group for each subset, which we can remove using `ṖṖ€`.
> 4 votes

# Answer
# Pyth, 11 bytes

```
m-@Fds-Qdty

```

Test suite.

## How it works

Each region of the Venn diagram represents elements that are in \[certain combinations of the sets\] but not in \[the other sets\].

So, we generate all the possible combinations (and remove the empty combinations) by finding the power set of the input.

For each combination generated, we find the intersection of the sets in the combination, and filter out the elements which are in the other sets.

```
m-@Fds-Qdty  input as Q
          y  power set
         t   remove the first one (empty combination)
m            for each combination d:
  @Fd            find the intersection of all the sets in d
 -               filter out those who are in
     s               the union of
      -Qd            the sets not in the combination
                     (input minus combination)

```
> 3 votes

# Answer
## JavaScript (ES6), 123 bytes

```
a=>a.map((b,i)=>b.map(e=>m[e]|=1<<i),m=[])&&[...Array(1<<a.length)].map((_,i)=>m.map((e,j)=>e==i&&j).filter(j=>j)).slice(1)

```
> 2 votes

---
Tags: code-golf, set-theory
---


# Question
Title: Create a black window with as little memory as possible
Today I installed MonoGame and ran the test application, which creates a basic colored window. I was surprised to see that the process was using 32.2 MiB of memory, and I thought it could be improved.

Your challenge is to write a program that creates a 640 by 480 window displaying only black pixels. Whatever program uses the least physical memory to do so wins. You may use any operating system released after the year 2000.

# Answer
# C, 96KiB

Never seen `restricted-memory` but i guess code length doesn't matter here. RAM usage was taken from gnome-system-monitor (i hope it's accurate).

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

#include <xcb/xcb.h>

int main ()
{
  xcb_connection_t    *c;
  xcb_screen_t        *screen;
  xcb_drawable_t       win;
  xcb_generic_event_t *e;
  uint32_t             values[2];

  char string[] = " ";

  c = xcb_connect (NULL, NULL);
  screen = xcb_setup_roots_iterator (xcb_get_setup (c)).data;
  win = screen->root;

  win = xcb_generate_id(c);
  values[0] = screen->black_pixel;
  values[1] = XCB_EVENT_MASK_EXPOSURE | XCB_EVENT_MASK_KEY_PRESS;
  xcb_create_window (c,XCB_COPY_FROM_PARENT,win,screen->root,
  0, 0,640,480,10,XCB_WINDOW_CLASS_INPUT_OUTPUT,screen->root_visual,XCB_CW_BACK_PIXEL | XCB_CW_EVENT_MASK, values);

  xcb_map_window (c, win);
  xcb_flush (c);

  while ((e = xcb_wait_for_event (c))) {
    switch (e->response_type & ~0x80) {
    case XCB_EXPOSE:
      xcb_flush (c);
      break;
    }
    free (e);
  }
  return 0;
}

```

This code works on pretty much every linux with a running xserver. To compile add `-lxcb` for the xcb libs.
> 0 votes

---
Tags: code-challenge
---


title: Mixed Base Conversion

text:
# Question
Title: Mixed Base Conversion
## Background

Most people on here should be familiar with several base systems: decimal, binary, hexadecimal, octal. E.g. in the hexadecimal system, the number *1234516* would represent

```
1*16^4 + 2*16^3 + 3*16^2 + 4*16^1 + 5*16^0

```

Note that we're usually not expecting the base (here, `16`) to change from digit to digit.

A generalisation of these usual positional systems allows you to use a different numerical base for each digit. E.g. if we were alternating between decimal and binary system (starting with base 10 in the least significant digit), the number *190315\[2,10\]* would represent

```
1*10*2*10*2*10 + 9*2*10*2*10 + 0*10*2*10 + 3*2*10 + 1*10 + 5 = 7675

```

We denote this base as `[2,10]`. The right-most base corresponds to the *least* significant digit. Then you go through the bases (to the left) as you go through the digits (to the left), wrapping around if there are more digits than bases.

For further reading, see Wikipedia.

## The Challenge

Write a program or function which, given a list of digits `D` an input base `I` and an output base `O`, converts the integer represented by `D` from base `I` to base `O`. You may take input via STDIN, ARGV or function argument and either return the result or print it to STDOUT.

You may assume:

* that the numbers in `I` and `O` are all greater than `1`.
* the `I` and `O` are non-empty.
* that the input number is valid in the given base (i.e., no digit larger than its base).

`D` could be empty (representing `0`) or could have leading zeroes. Your output should not contain leading zeroes. In particular, a result representing `0` should be returned as an empty list.

You must not use any built-in or 3rd-party base conversion functions.

This is code golf, the shortest answer (in bytes) wins.

## Examples

```
D               I                  O        Result
[1,0,0]         [10]               [2]      [1,1,0,0,1,0,0]
[1,0,0]         [2]                [10]     [4]
[1,9,0,3,1,5]   [2,10]             [10]     [7,6,7,5]
[1,9,0,3,1,5]   [2,10]             [4,3,2]  [2,0,1,1,0,1,3,0,1]
[52,0,0,0,0]    [100,7,24,60,60]   [10]     [3,1,4,4,9,6,0,0]
[0,2,10]        [2,4,8,16]         [42]     [1,0]
[]              [123,456]          [13]     []
[0,0]           [123,456]          [13]     []

```

# Answer
# CJam, 45

```
q~_,@m>0@{@(:T+@T*@+}/\;La{\)_@+@@md@@j@+}jp;

```

Finally I found a good use of `j`.

### How it works

`Long ArrayList Block j` executes the block which takes an integer as the parameter, and `Long j` will call this block recursively in the block. It will also store the values returned by the block in an internal array, which is initialized by the array parameter. It will not execute the block if the input is already in the array, and the value in the array is returned instead.

So if I initialize it with an array of an empty array, the empty array will be returned for input 0, and the block will be executed for any other input.

```
q~_,@m>0@{@(:T+@T*@+}/\;     " See below. Stack: O decoded-D ";
La                           " Initialized the value with input 0 as empty list. ";
{
  \)_@+@@md@@                " See below. Stack: remainder O quotient ";
  j                          " Call this block recursively except when the same quotient has
                               appeared before, which is impossible except the 0.
                               Stack: remainder O returned_list ";
  @+                         " Append the remainder to the list. ";
}j
p;                           " Format and output, and discard O. ";

```

# CJam, 49 48

```
q~_,@m>0@{@(:T+@T*@+}/\;{\)_@+@@md@@}h;;_{}?]W%`

```

Input should be `O I D`.

Examples:

```
$ while read; do <<<$REPLY ./cjam-0.6.2.jar <(echo 'q~_,@m>0@{@(:T+@T*@+}/\;{\)_@+@@md@@}h;;_{}?]W%`');echo; done
[2] [10] [1 0 0]
[10] [2] [1 0 0]
[10] [2 10] [1 9 0 3 1 5]
[4 3 2] [2 10] [1 9 0 3 1 5]
[10] [100 7 24 60 60] [52 0 0 0 0]
[42] [2 4 8 16] [0 2 10]
[13] [123 456] []
[13] [123 456] [0 0]
[1 1 0 0 1 0 0]
[4]
[7 6 7 5]
[2 0 1 1 0 1 3 0 1]
[3 1 4 4 9 6 0 0]
[1 0]
""
""

```

### How it works

```
q~           “ Read the input and evaluate. ";
_,@m>        " Rotate I to the right by the length of D. ";
0@{          " For each item in D, with the result initialized to 0: ";
  @(:T+      " Rotate I to the left, and set the original first item to T. ";
  @T*@+      " Calculate result * T + current. ";
}/
\;           " Discard I. ";
{            " Do: ";
  \)_@+      " Rotate O to the right, and get a copy of the original last item. ";
  @@md       " Calculate divmod. ";
  @@         " Move O and the quotient to the top of the stack. ";
}h           " ...while the quotient is not 0. ";
;;           " Discard O and the last 0. ";
_{}?         " If the last item is still 0, discard it. ";
]W%          " Collect into an array and reverse. ";
`            " Turn the array into its string representation. ";

```
> 6 votes

# Answer
# CJam, ~~62~~ ~~61~~ ~~59~~ 57 bytes

```
q~Wf%~UX@{1$*@+\@(+_W=@*@\}/;\;{\(+_W=@\md@@}h;;]W%_0=!>p

```

Reads the input arrays as `[O I D]` from STDIN. Try it online.

### How it works

```
q~         " Read from STDIN and evaluate the input. Result: [O I D]                      ";
Wf%~       " Reverse each of the three arrays and dump them on the stack.                 ";
UX@        " Push U (0) and X (1); rotate D on top of both.                               ";
{          " For each N in D:                                                             ";
  1$*      "   N *= X                                                                     ";
  @+       "   U += N                                                                     ";
  \@(+     "   I := I[1:] + I[:1]                                                         ";
  _W=@*    "   X *= I[-1]                                                                 ";
  @\       "   ( U I X ) ↦ ( I U X )                                                      ";
}/         "                                                                              ";
;\;        " Discard I and X.                                                             ";
{          " R := []; Do:                                                                 ";
  \(+      "   O := O[1:] + O[:1]                                                         ";
  _W=@\md  "   R += [U / O[-1]], U %= O[-1]                                               ";
  @@       "   ( O U R[-1] ) ↦ ( R[-1] O U )                                              ";
}/         " While U                                                                      ";
;;]        " Discard U and O.                                                             ";
W%         " Reverse R.                                                                   ";
_0=!>      " Execute R := R[!R[0]:] to remove a potential leading zero.                   ";
p          " Print a string presentation of R.                                            ";

```

### Test cases

```
$ cjam mixed-base.cjam <<< '[ [2]     [10]             [1 0 0]       ]'
[1 1 0 0 1 0 0]
$ cjam mixed-base.cjam <<< '[ [10]    [2]              [1 0 0]       ]'
[4]
$ cjam mixed-base.cjam <<< '[ [10]    [2 10]           [1 9 0 3 1 5] ]'
[7 6 7 5]
$ cjam mixed-base.cjam <<< '[ [4 3 2] [2 10]           [1 9 0 3 1 5] ]'
[2 0 1 1 0 1 3 0 1]
$ cjam mixed-base.cjam <<< '[ [10]    [100 7 24 60 60] [52 0 0 0 0]  ]'
[3 1 4 4 9 6 0 0]
$ cjam mixed-base.cjam <<< '[ [42]    [2 4 8 16]       [0 2 10]      ]'
[1 0]
$ cjam mixed-base.cjam <<< '[ [13]    [123 456]        []            ]'
""
$ cjam mixed-base.cjam <<< '[ [13]    [123 456]        [0 0]         ]'
""

```

Note that empty strings and empty arrays are indistinguishable to CJam, so `[]p` prints `""`.
> 3 votes

# Answer
# Python 2 - 318

```
from operator import *
d,i,o=input()
c=len
def p(l):return reduce(mul,l,1)
n=sum(x[1]*p((i[-x[0]%c(i)-1:]+x[0]/c(i)*i)[1:]) for x in enumerate(d[::-1]))
r=[]
j=1
t=[]
k=c(o)
while p(t)*max(o)<=n:t=(o[-j%k-1:]+j/k*o)[1:];j+=1
while j:j-=1;t=(o[-j%k-1:]+j/k*o)[1:];r+=[n/p(t)];n%=p(t)
print (r if r[0] else [])

```

~~I messed up the order of the arguments by accident, so I had to reverse them. I will work on the slice-fu to get the lists to work in the other direction later, I already wasted my entire lunch break :p~~

Fixed
> 2 votes

# Answer
# Python 2 - 122

Very straightforward, didn't manage to find any special golf tricks on this one.

```
def f(D,I,O):
 n,i,l=0,-len(D),[]
 for d in D:n=n*I[i%len(I)]+d;i+=1
 while n:i-=1;b=O[i%len(O)];l=[n%b]+l;n/=b
 return l

```

Ungolfed:

```
def f(D,I,O):
    n = 0
    for i in range(len(D)):
        dn = len(D) - i
        n = n * I[-dn % len(I)] + D[i]
    l = []
    i = 0
    while n:
        i -= 1
        b = O[i%len(O)]
        l = [n%b] + l
        n /= b
    return l

```

### Edit: 116-byte program version thanks to FryAmTheEggman

```
D,I,O=input()
n,i,l=0,-len(D),[]
for d in D:n=n*I[i%len(I)]+d;i+=1
while n:i-=1;b=O[i%len(O)];l=[n%b]+l;n/=b
print l

```

This version accepts comma-separated input e.g. `[1,9,0,3,1,5], [2,10], [10]`
> 2 votes

# Answer
# APL, 78

```
{1↓(⊃1⌷⍺)({t←⍺[(⍴⍺)|⍴⍵]
(⌊0⌷⍵÷t)(t|0⌷⍵),1↓⍵}⍣{0=0⌷⍵}),+/(0,⍵)×⌽×\1,(⍴⍵)⍴⌽⊃0⌷⍺}

```

Examples:

```
f←{1↓(⊃1⌷⍺)({t←⍺[(⍴⍺)|⍴⍵]
  (⌊0⌷⍵÷t)(t|0⌷⍵),1↓⍵}⍣{0=0⌷⍵}),+/(0,⍵)×⌽×\1,(⍴⍵)⍴⌽⊃0⌷⍺}
(,10)(,2) f 1 0 0
1 1 0 0 1 0 0
(,2)(,10) f 1 0 0
4
(2 10)(,10) f 1 9 0 3 1 5
7 6 7 5
(2 10)(4 3 2) f 1 9 0 3 1 5
2 0 1 1 0 1 3 0 1
(100 7 24 60 60)(,10) f 52 0 0 0 0
3 1 4 4 9 6 0 0
(2 4 8 16)(,42) f 0 2 10
1 0
(123 456)(,13) f ⍬

⍴(123 456)(,13) f ⍬
0
(123 456)(,13) f 0 0

⍴(123 456)(,13) f 0 0
0

```
> 2 votes

# Answer
# k2 - ~~83~~ 74 char

Function taking one argument. This was just a lot better suited for K than J, which is why I'm not using J. It would just be a load of boxing/unboxing garbage, and nobody wants that. This is in the k2 dialect (may require some adaptation to work in the open source implementation Kona), but I'll change this to k4 if I can golf it down shorter there.

```
{:[#x@:|&~&\~x;|*{x 1}.[{_(x,y!*z;y%*z;1!z)}]/(();+/x*1*\(1-#x)#y;|z);()]}

```

I will note that I take a stand for pickiness here and say that one item lists have to be input as such. `,2` is a list of one item, that item being the scalar `2`. Often scalars and 1-item lists are interchangable, but there is logic in this golf that relies on the assumption of list arguments.

To explain the golf, I'll break it into two parts. `F` is the golf, `L` is the main loop that calculates the output. The exact mechanism of the looping is that `L` is applied to its arguments repeatedly until the second argument is zero, then that result is returned. (This is the `.[L]/` part.)

```
L: {_(x,y!*z;y%*z;1!z)}
F: {:[#x@:|&~&\~x;|*{x 1}.[L]/(();+/x*1*\(1-#x)#y;|z);()]}

```

By explosion:

```
{_(x,y!*z;y%*z;1!z)}  /function, args x y z
  (      ;    ;   )   / update each arg as follows:
               1!z    /  new z: rotate z left
            *z        /  head of z (current base digit)
          y%          /  y divided by that
 _                    /  new y: floor of that
     y!*z             /  y modulo head of z
   x,                 /  new x: append that to old x

{:[#x@:|&~&\~x;|*{x 1}.[L]/(();+/x*1*\(1-#x)#y;|z);()]}  /function, args x y z
            ~x                                           /find the 0s in x
          &\                                             /find leading zeros
        &~                                               /indices of digits that aren't
    x@ |                                                 /those items from x, reverse order
    x :                                                  /assign to x
 :[#          ;                                      ]   /if length is 0:
                                                   ()    / return empty list
                                                  ;      /else:
                      .[L]/                              / loop L repeatedly
                 {x 1}                                   / until y = 0
                           (  ;               ;  )       / starting with args:
                            ()                           /  Lx: empty list
                                       1-#x              /  number of input digits, minus 1
                                      (    )#y           /  cyclically extend base leftward
                                   1*\                   /  running product, start at 1
                                 x*                      /  multiply digits by these
                               +/                        /  Ly: sum of the above
                                               |z        /  Lz: out base, reverse order
               |*                                        / first elem of result, reversed

```

In action:

```
  {:[#x@:|&~&\~x;|*{x 1}.[{_(x,y!*z;y%*z;1!z)}]/(();+/x*1*\(1-#x)#y;|z);()]}[1 0 0; ,10; ,2]
1 1 0 0 1 0 0
  f:{:[#x@:|&~&\~x;|*{x 1}.[{_(x,y!*z;y%*z;1!z)}]/(();+/x*1*\(1-#x)#y;|z);()]}
  f[1 0 0; ,2; ,10]
,4
  f .' ((1 9 0 3 1 5; 2 10;           ,10)  /f apply each
>       (1 9 0 3 1 5; 2 10;           4 3 2)
>       (52 0 0 0 0;  100 7 24 60 60; ,10)
>       (0 2 10;      2 4 8 16;       ,42)
>       (();          123 456;        ,13)
>       (0 0;         123 456;        ,13))
(7 6 7 5
 2 0 1 1 0 1 3 0 1
 3 1 4 4 9 6 0 0
 1 0
 ()
 ())

```
> 1 votes

# Answer
# Perl 6, 67 bytes

```
{[R,] [+]([R,](@^a)Z*1,|[\*] |[R,](@^b)xx*).polymod: |[R,](@^c)xx*}

```

Try it

## Expanded:

```
{  # bare block lambda with placeholder parameters @a,@b,@c

  [R,]    # reduce the following using reverse meta op ｢R｣ combined with ｢,｣ op
          # (shorter than ｢reverse｣)

    [+](  # sum

        [R,](@^a) # reverse of first argument

      Z[*]        # zipped using &infix:<*> with the following

        1,
        |                    # slip the following in (flattens)
          [\*]               # triangle reduce

            |[R,](@^b) xx*   # reverse of second argument repeated infinitely
    )

    .polymod: |[R,](@^c) xx* # moduli the reverse of third argument repeated
}

```

---

In case you aren't sure what triangle reduce does:

```
[\*] 1,2,3,4,5
# 1, 1*2, 1*2*3, 1*2*3*4, 1*2*3*4*5
# 1,   2,     6,      24,       120

```

---

If I could take the inputs reversed, and output the reverse, it would be 47 bytes.

```
{[+](@^a Z*1,|[\*] |@^b xx*).polymod: |@^c xx*}

```

Try it
> 0 votes

---
Tags: code-golf, number, arithmetic, number-theory, base-conversion
---


# Question
Title: Divide and stay Happy. Who cares about the Conquer part?
Well, when I buy gifts for my two wives, I want them to feel equally important to me, but it's hard to go shopping with fixed budgets. Instead, I buy a bunch of stuff and divide them into two groups with as equal value as possible. Then I buy a bunch of chocolates to fix the rest.

But I don't want do all the hard lifting when my computer can do it. And you don't either. So solve this problem so that the next time you need to divide gifts among your wives, you know it would be easy.

### Input

1 array of (N\*2) elements where N\*2 is specified in the 1st line.
The elements of the array in the following line.

### Output

2 array of N elements each such that:
Difference of (Sum of elements of array 1) and (Sum of elements of array 2) is as close as possible to 0.

## Example

### Input

```
4
1 2 3 4

```

### Output

```
1 4
2 3
diff=0

```

**Disclaimer**: I don't have two wives. But when I feel bad, I imagine having two wives. And suddenly, I am thankful and happy that I have only one. :D

# Answer
# Java

Trying to solve this problem in two phases:

1. Build two equally sized lists by adding the remaining biggest to the currently smaller list and the next to the other. Repeat.
2. Identify items from both lists that can be switched to reduce the difference in value

Input like

> ```
> 8
> 1 2 3 4 5 6 7 8
>
> ```

is already solved after phase 1 as e.g.

> ```
> 2 3 5 8
> 1 4 6 7
> diff=0
>
> ```

and input like

> ```
> 6
> 1 4 5 6 7 8
>
> ```

will need both phases so that

> ```
> 1 5 8
> 4 6 7
> diff=3
>
> ```

(after phase one) becomes the result of

> ```
> 1 6 8
> 4 5 7
> diff=1
>
> ```

While I can guarantee this attempt will always provide a solution, I can not prove that a optimal solution is found in all cases. With the restriction of equally sized lists it however feels quite realistic that there are no corner cases left behind. Prove me wrong ;-)

Program on ideone.com

```
import java.util.*;

/**
 * Created to solve http://codegolf.stackexchange.com/q/23461/16293 .
 */
public class EqualSums {

    public static void main(String[] args) {
        final Scanner s = new Scanner(System.in);
        // Read number of elements to divide
        final int count = s.nextInt();
        if (count % 2 == 1) {
            throw new IllegalStateException(count + " can not be divided by 2. Consider adding a 0 value.");
        }
        // Read the elements to divide
        final SortedList valueStack = new SortedList(count);
        for (int i = 0; i < count; i++) {
            valueStack.add(s.nextLong());
        }

        final SortedList targetOne = new SortedList(count / 2);
        final SortedList targetTwo = new SortedList(count / 2);
        // Divide elements into two groups
        addInPairs(targetOne, targetTwo, valueStack);
        // Try to ensure groups have equal value
        retaliate(targetOne, targetTwo);

        // Output result
        System.out.println(targetOne);
        System.out.println(targetTwo);
        System.out.println("diff=" + Math.abs(targetOne.getSum() - targetTwo.getSum()));
    }

    private static void addInPairs(SortedList targetOne, SortedList targetTwo, SortedList valueStack) {
        SortedList smallerTarget = targetOne;
        SortedList biggerTarget = targetTwo;
        while (!valueStack.isEmpty()) {
            // Add biggest remaining value to small target
            smallerTarget.add(valueStack.removeLast());

            // Add second biggest remaining value to big target
            biggerTarget.add(valueStack.removeLast());

            // Flip targets if roles have changed
            if (smallerTarget.getSum() > biggerTarget.getSum()) {
                final SortedList temp = smallerTarget;
                smallerTarget = biggerTarget;
                biggerTarget = temp;
            }
        }

    }

    private static void retaliate(SortedList targetOne, SortedList targetTwo) {
        long difference;
        boolean changed;
        outer:
        do {
            difference = Math.abs(targetOne.getSum() - targetTwo.getSum());
            if (difference == 0) {
                return;
            }
            changed = false;
            // Try to find two values, that reduce the difference by changing them between targets
            for (Long valueOne : targetOne) {
                for (Long valueTwo : targetTwo) {
                    final Long tempOne = targetOne.getSum() + valueTwo - valueOne;
                    final Long tempTwo = targetTwo.getSum() - valueTwo + valueOne;
                    if (Math.abs(tempOne - tempTwo) < difference) {
                        targetOne.remove(valueOne);
                        targetTwo.add(valueOne);
                        targetTwo.remove(valueTwo);
                        targetOne.add(valueTwo);
                        changed = true;
                        continue outer;
                    }
                }
            }
        } while (changed);
    }

    public static class SortedList extends AbstractList<Long> {

        private final ArrayList<Long> list;
        private long sum = 0;

        public SortedList(int count) {
            list = new ArrayList<>(count);
        }

        // the next functions access list-field directly
        @Override
        public Long get(int index) {
            return list.get(index);
        }

        @Override
        public boolean add(final Long t) {
            final int i = Collections.binarySearch(list, t);
            if (i < 0) {
                // No equal element present
                list.add(-i - 1, t);
            } else {
                list.add(afterLastEqual(i, t), t);
            }
            sum += t;
            return true;
        }

        @Override
        public Long remove(int index) {
            final Long old = list.remove(index);
            sum -= old;
            return old;
        }

        @Override
        public int size() {
            return list.size();
        }

        // the next functions access list-field only through the functions above this point
        // to ensure the sum is well kept

        public long getSum() {
            return sum;
        }

        private int afterLastEqual(final int start, Object o) {
            int found = start;
            while (found < size() && o.equals(get(found))) {
                found++;
            }
            return found;
        }

        private int beforeFirstEqual(final int start, final Object o) {
            int found = start;
            while (found >= 0 && o.equals(get(found))) {
                found--;
            }
            return found;
        }

        @Override
        public int indexOf(Object o) {
            try {
                final int i = Collections.binarySearch(this, (Long) o);
                if (i >= 0) {
                    return beforeFirstEqual(i, o) + 1;
                }
            } catch (ClassCastException e) {
                // Object was not instance of Long
            }
            return -1;
        }

        @Override
        public int lastIndexOf(Object o) {
            try {
                final int i = Collections.binarySearch(this, (Long) o);
                if (i >= 0) {
                    return afterLastEqual(i, o) - 1;
                }
            } catch (ClassCastException e) {
                // Object was not instance of Long
            }
            return -1;
        }

        @Override
        public boolean remove(Object o) {
            if (o == null) {
                return false;
            }
            final int i = indexOf(o);
            if (i >= 0) {
                remove(i);
                return true;
            }
            return false;
        }

        public Long removeLast() {
            return remove(size() - 1);
        }

        public Long removeFirst() {
            return remove(0);
        }

        @Override
        public String toString() {
            Iterator<Long> it = iterator();
            if (!it.hasNext()) {
                return "";
            }

            StringBuilder sb = new StringBuilder();
            for (; ; ) {
                Long e = it.next();
                sb.append(e);
                if (!it.hasNext()) {
                    return sb.toString();
                }
                sb.append(' ');
            }
        }
    }
}

```
> 4 votes

# Answer
# Brachylog 2

```
pᶠḍᵐ{+ᵐo-}ᵒh

```

Try it online!

This is a popularity contest, but that doesn't necessarily mean that golfing languages are a bad fit. (Really, I should have answered in Jelly because Jelly answers tend to get a disproportionate number of upvotes for some reason regardless of who submits them or how golfed they are, but Brachylog is more readable.)

We start off by taking the list of all permutations of the input (`pᶠ`), and splitting each () into two equal pieces (; we could give it a subscript if you had more than two wives for some reason). Then we order the split permutations (`{…}ᵒ`) by taking the sum (`+`) of each () half, taking the absolute difference (i.e. `o-`, "ordered difference"), and using those differences to define the sort order. The best result is the first one, so we take the head of the list with `h` to get the result.
> 3 votes

# Answer
# Mathematica

Input forms

The input string is to be taken through STDIN. `assets` refers to the amounts to be distributed among the wives (or twins). `length` is the number of assets.

```
assets=ToExpression[Rest[s=StringSplit[input]]]
length=ToExpression[First[s]]

```

For the present purposes we will assume that the assets consist of the integers from 1 through 20.

```
assets=Range[20];
length=Length[Range[20]]

```

**Processing**

```
(* find all possible distributions to one wife; the other presumably gets the remaining assets *)
r=Subsets[assets,{length/2}];

(*order them according to the difference with respect to the total of half of the assets.
Remove the first set of assets.  One wife will get these.*)
s=SortBy[r/.{{a__Integer}:> {{a},Abs[Tr[Range[20]/2]-Tr[{a}]]}},Last][[1]];

(*The other wife's assets will be the complement.  The difference is carried over from the sorting routine. *)
Grid[{{Grid[{s[[1]],Complement[assets,s[[1]]]}]},{"difference = "<>ToString[s[[2]]]}}]

```

---

## Is the distribution unfair? So, choose another.

@The Constructor notes that wife 2 may contest the fact that wife 1 got all the best assets. So the following produces all of the "fair" (difference = lowest difference) shares for wife 1; wife 2 gets the remaining assets; the zero refers to the difference in assets for the wives. There are 5448 ways to distribute assets weighted 1 through 20. Only a few lines are displayed.

The format is

```
s=SortBy[r/.{{a__Integer}:> {{a},Abs[Tr[Range[20]/2]-Tr[{a}]]}},Last];
z=Cases[s,{_List,x_}/;x==s[[1,2]]];
Short[z,10]
Length[z]

```

> {{{1,2,3,4,5,16,17,18,19,20},0},{{1,2,3,4,6,15,17,18,19,20},0},{{1,2,3,4,7,14,17,18,19,20},0},{{1,2,3,4,7,15,16,18,19,20},0},{{1,2,3,4,8,13,17,18,19,20},0},{{1,2,3,4,8,14,16,18,19,20},0},{{1,2,3,4,8,15,16,17,19,20},0},{{1,2,3,4,9,12,17,18,19,20},0},{{1,2,3,4,9,13,16,18,19,20},0},{{1,2,3,4,9,14,15,18,19,20},0},{{1,2,3,4,9,14,16,17,19,20},0},{{1,2,3,4,9,15,16,17,18,20},0},{{1,2,3,4,10,11,17,18,19,20},0},{{1,2,3,4,10,12,16,18,19,20},0}, \<\<5420\>\>, {{5,6,7,8,9,11,13,14,15,17},0},{{5,6,7,8,9,12,13,14,15,16},0},{{5,6,7,8,10,11,12,13,14,19},0},{{5,6,7,8,10,11,12,13,15,18},0},{{5,6,7,8,10,11,12,13,16,17},0},{{5,6,7,8,10,11,12,14,15,17},0},{{5,6,7,8,10,11,13,14,15,16},0},{{5,6,7,9,10,11,12,13,14,18},0},{{5,6,7,9,10,11,12,13,15,17},0},{{5,6,7,9,10,11,12,14,15,16},0},{{5,6,8,9,10,11,12,13,14,17},0},{{5,6,8,9,10,11,12,13,15,16},0},{{5,7,8,9,10,11,12,13,14,16},0},{{6,7,8,9,10,11,12,13,14,15},0}}
>
> 5448

---

The prior submission can be found among the edits. It is far more inefficient, relying as it does on `Permutations`.
> 2 votes

# Answer
# J

There's a cheat sheet of all the J primitives at this link, in case you want to follow along at home. Remember: J is generally read from right to left, so that `3*2+1` is 7, not 9. Every verb (J for function) is either monadic, so in front like `f y`, or dyadic, so in between like `x f y`.

```
N =: (". 1!:1 ] 1) % 2          NB. number of items per wife
S =: ". 1!:1 ] 1                NB. list of items to distribute

bins =: #: i. 2 ^ 2*N           NB. all binary strings of length 2n
even =: bins #~ N = +/"1 bins   NB. select those with row-sum 1

NB. all distributions of equal numbers of items to each wife
NB. resultant shape: a list of 2xN matrices
NB. this /. adverb is where all the magic happens, see below
dist =: even ]/."1 S

diff =: | -/"1 +/"1 dist        NB. difference in wives' values
idx  =: (i. <./) diff           NB. index of the lowest difference

1!:2&2 idx { dist               NB. print the winning distribution of items
1!:2&2 'diff=', idx { diff      NB. and the difference of that distribution

```

Notes and explanations:

* `u/` means "fold `u` over", so perform the binary operation over each element in the list. So for example: `+/` means *Fold Plus*, or **Sum**; `<.` is *Lesser Of*, so `<./` means *Fold Lesser Of*, or **Minimum**.
* `u"1` means "perform `u` on 1-dimensional cells", i.e. over every row. Normally the verbs in J are either atomic, or apply to the whole argument. This applies to both arguments if the verb is used dyadically (with two arguments). Consider the following:

```
   i. 2 3        NB. just a 2x3 matrix of numbers
0 1 2
3 4 5
   +/   i. 2 3   NB. Sum the items
3 5 7
   +/"1 i. 2 3   NB. Sum the items of each row
3 12

```
* `#:` is a verb that expands a number into its binary representation. When you use it on a list with more than one element, it will also align all the numbers properly, so that `#:i.2^n` will get you every binary string of length `n`.
* `/.`, when used dyadically, is called *Key*. It uses the elements of the list on the left side as keys, and those on the right side as values. It groups together each set of values that share a key, and then performs some operation on them.

In the case of `]/.`, the operation is just the identity verb, so nothing altogether special is happening there, but the fact that `/.` will partition up the list for us is the important bit. This is why we create the binary lists: so that for each list (`"1`), we can divvy up the gifts for the wives in all possible ways.
* `1!:1]1` and `1!:2&2` are the read-in and write-out operations, respectively. The `1!:n` part is the verb and the other number is the file handle. `1` is console in, `2` is console out, and `3 4 5` are stdin, stdout, and stderr. We also use `".` when reading so that we convert the input strings to numbers.
> 2 votes

# Answer
## MATLAB

Here is my solution:

```
%input array
presents=zeros(2,8);
presents(1,1)=8; %number of presents
presents(2,:)=[1 2 7 4 5 3 2 8]; %list of presents

%calculate the cumulative sum of all permutations
%its all about the gift values
how_many=presents(1,1);
options=perms(presents(2,:);
subtotals=cumsum(options,2);

%find the first index where the difference between the two parts is minimal
%makes both wives happy!!
[~, double_happiness] = min(abs(sum(presents(2,:))/2-subtotals(:,how_many/2)));

%create the present lists for Jennifer and Kate :)
for_jennifer=options(double_happiness,1:how_many/2)
for_kate=options(double_happiness,how_many/2+1:end)

```

For example the present list in my source code results in:

```
for_jennifer =

     8     2     5     1

for_kate =

     4     7     2     3

```

which is both 16.

If I golf my code, which is less fun I get a very unoptimised 132 chars. Beat that ;)

```
function f(p);o=perms(p(:,2));s=cumsum(o,2);[~,d]=min(abs(sum(p(:,2))/2-s(:,p(1,1)/2)));a={o(d,1:p(1,1)/2);o(d,p(1,1)/2+1:end)};a{:}

```
> 1 votes

# Answer
# Clojure

```
(defn divide [n]
 (loop [lv [] rv [] d (reverse (sort n))]
  (if (empty? d)
   [lv rv]
   (if (> (reduce + lv) (reduce + rv))
     (if (>= (count lv ) (count rv))
       (recur lv (conj rv (first d)) (into [] (rest d)))
       (recur (conj lv (last d)) rv (pop d)))
     (if (<= (count lv ) (count rv))
       (recur (conj lv (first d)) rv (into [] (rest d)) )
       (recur lv (conj rv (last d)) (pop d)))))))

 (defn display [[f s]]
   (println f)
   (println s)
   (println (str "Diff " (- (reduce + f) (reduce + s)))))

```

Test

```
 (->>
 [5 1 89 36 2 -4 20 7]
 divide
 display)

 =: [89 -4 1 2]
    [36 20 7 5]
    Diff 20

```
> 1 votes

# Answer
## PHP

**Warning:** Very dirty code
It tries every possible permutation of the input array.

Ideone sample for `4/1 2 3 4`: http://ideone.com/gIi174

```
<?php
// Discard the first input line! It's useless :)
fgets(STDIN);
$numbers = explode(' ', rtrim(fgets(STDIN)));
$valuePerWife = array_sum($numbers) / 2;

// Taken from here: http://stackoverflow.com/a/13194803/603003
// Credits to dAngelov: http://stackoverflow.com/users/955185/dangelov
function pc_permute($items, $perms = array( )) {
    if (empty($items)) {
        $return = array($perms);
    }  else {
        $return = array();
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
         list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             $return = array_merge($return, pc_permute($newitems, $newperms));
         }
    }
    return $return;
}

foreach (pc_permute($numbers) as $permutation) {
    $sum = 0;
    $rest = [];

    for ($i=0; $i<count($permutation); $i++) {
        $sum += $permutation[$i];
        if ($sum == $valuePerWife) {
            $rest = array_slice($permutation, $i + 1);
            break;
        }
    }

    if (array_sum($rest) == $valuePerWife) {
        echo implode(' ', array_slice($permutation, 0, $i + 1)), "\n";
        echo implode(' ', array_slice($permutation, $i + 1)), "\n";
        echo 'diff=0';
        exit;
    }
}
exit('DIDNT FOUND ANY COMBINATION!');

```
> 0 votes

# Answer
## Literate Haskell

```
> import Data.List
> import Data.Function

```

I made use of the list monad to split it up.

```
> divide []=return ([], [])
> divide (x:xs)=do
>   (w1, w2) <- divide xs
>   [(x:w1, w2), (w1, x:w2)]

```

Then we make a rater.

```
> rating (w1, w2)=abs $ (sum w1) - (sum w2)

```

And then a function that will minimize the difference.

```
> best = minimumBy (compare `on` rating) . filter (\(x,y)->length x == length y)

```

And something that combines them all.

```
> bestDivison=best . divide

```

Next a parser.

```
> parse::String->[Int]
> parse=fmap read . words

```

And an output formatter.

```
> output (w1,w2)=unlines [unwords (map show w1)
>                        , unwords ( map show w2)
>                        , "diff="++(show $ abs $ (sum w1) - (sum w2))]

```

And now the program

```
> main = do
>   getLine --Ignored, I don't need the arrays length
>   input <- fmap parse getLine
>   putStrLn "" --For readability
>   putStrLn $ output $ bestDivison input

```

Example:

```
λ <*Main>: main
8
5 1 89 36 2 -4 20 7

5 36 20 7
1 89 2 -4
diff=20

```
> 0 votes

# Answer
## Python:

```
import itertools as t
raw_input()
a=[int(i) for i in raw_input().split()]
a=list(t.permutations(a))
b=len(a[0])/2
c=[(d[b:],d[:b]) for d in a]
d=[abs(sum(d[b:])-sum(d[:b])) for d in a]
e=zip(d,c)
e.sort()
print " ".join([str(i) for i in e[0][1][0]])
print " ".join([str(i) for i in e[0][1][1]])
print "diff",e[0][0]

```

or a bit golfified:

```
import itertools as t
b=int(raw_input())/2
e=[(abs(sum(d[b:])-sum(d[:b])),(d[b:],d[:b])) for d in t.permutations([int(i) for i in raw_input().split()])]
e.sort()
f=e[0]
g=f[1]
print " ".join([str(i) for i in g[0]]),"\n"," ".join([str(i) for i in g[1]]),"\n","diff=",f[0]

```

Or even further golfified, since half the lines is just makeup. (assuming I can just dump the raw internal array, since this isn't specified in the op) You can leave away the `print` in (for example) the interactive shell, and add a `[::-1]` (on the very end, after `[0]`) if you really want the diff last.

```
import itertools as t
b=int(raw_input())/2
print sorted([(abs(sum(d[b:])-sum(d[:b])),(d[b:],d[:b])) for d in t.permutations([int(i) for i in raw_input().split()])])[0]

```

(results in `(0, ((1, 2, 7, 8), (3, 4, 5, 6)))`)

This, however, is just bruteforcing all posible combinations, and shouldn't be considered remotely efficient. However, if the list being equal lengths doesn't matter, this would also work (on large arrays):

```
raw_input()
a,b=[],[]
for i in sorted([int(i) for i in raw_input().split()])[::-1]:
    b.append(i)
    if sum(b)>sum(a): b,a=a,b
print a,b,abs(sum(b)-sum(a))

```

With the code under this for example, it runs with barely a difference at all: 500k on 10^10 max value isn't a lot, so to say. This is also a lot faster: where the other code probably wouldn't finish in under a year (and that's very optimistic), this runs in about half a second, even though your milage may vary.

```
def raw_input():
    import random
    return " ".join([str(random.randint(1,10**10)) for _ in range(10000)])

raw_input()
a,b=[],[]
for i in sorted([int(i) for i in raw_input().split()])[::-1]:
    b.append(i)
    if sum(b)>sum(a): b,a=a,b
print a,b,abs(sum(b)-sum(a))

```
> 0 votes

---
Tags: math, array, popularity-contest
---


title: Implement the Fibonacci-quine

text:
# Question
Title: Implement the Fibonacci-quine
A Quine is a program which outputs its source when run.

In this challenge, You should make a Fibonacci-quine, a variant of the quine.

---

## What is a Fibonacci-quine?

A Fibonacci-quine is a program, which outputs a modification of the source by the following rule:

The initial source should be `...2...`. In other words, the source should contain `2`. (Why 2? If it was 1, Nobody would know if it was the first 1 or the second, Even the program itself)

When run, You should output the source, but *only* the specific number (In this stage, `2`) changed to the next number of the fibonacci sequence. For example, `...3...`. Same goes for the output, and the output of the output, etc. You may support integers for up to 2^32-1. For integers over that limit, the next output is on your choice.

> ### OP's note
>
> I would really like to see a creative solution for this. I couldn't think of a single solution for this, since Both of the two important aspects of the challenge, fibonacci and quine, is not easy. I'll be waiting then!

# Answer
## Mathematica, 61 bytes

```
ToString[#0 /. v:2 :> RuleCondition[Round[GoldenRatio v]]] &

```

Note that there is a trailing space. This is a function quine, i.e. the above code evaluates to an unnamed function which, if called returns the code itself as a string (with `2` changed to the next Fibonacci number).

This was suprisingly tricky to get to work. The basic idea is to take the function itself (with `#0`) and replace a number in that function with the next one using `/. v:2 :> nextFib[v]`. However, `nextFib` wouldn't get evaluated at this stage so we wouldn't really end up with the new number in the source code. After searching around for a while to figure out how to force immediate evaluation, I found this great post on Mathematica.SE. The "standard" technique uses a `With` block which forces evaluation, but the second answer by WReach contains a shorter alternative using the undocumented built-in `RuleCondition` which also forces evaluation.

The way we compute the next Fibonacci number is by making use of the fact that the ratio of consecutive numbers is roughly the golden ratio **1.618...** and this is accurate up to rounding. So we don't need to keep track of the last two numbers and can simply do `Round[GoldenRatio v]`. This will never lose precision since Mathematica's `GoldenRation` is a symbolic value and therefore `Round` can always compute an accurate result.

In summary:

```
... #0 ... &

```

An unnamed function, where `#0` refers to the function object itself.

```
... /. v:2 :> ...

```

Find a `2` in the expression tree of the function (this `2` of course only matches itself), call it `v` and replace it with...

```
... RuleCondition[Round[GoldenRatio v]]

```

... the next Fibonacci number.

```
ToString[...]

```

And convert the resulting expression tree to its string representation.
> 8 votes

# Answer
## CJam, 26 bytes

```
2{0X{_@+_W$>!}go;\;"_~"}_~

```

Try it online!

Probably not quite optimal. We simply iterate the Fibonacci sequence until the value is greater than the last one and use the result as the new value at the beginning of the program.
> 7 votes

# Answer
# Python 3, 95 bytes

```
a=b=1
while a<2:a,b=b,a+b
s='a=b=1\nwhile a<%i:a,b=b,a+b\ns=%r;print(s%%(b,s))';print(s%(b,s))

```

Try it online!

Obviously a fork of Martin Ender's CJam answer.
> 7 votes

# Answer
# CJam, 20 bytes

```
2{\5mq)*)Y/io"_~"}_~

```

Try it online!
> 6 votes

# Answer
# Actually, 19 bytes

```
2⌠è@fuF$+";ƒ"@+⌡;ƒ

```

Try it online!

Obviously a fork of Martin Ender's CJam answer.
> 5 votes

# Answer
# Python 3, ~~81~~ 79 bytes

```
s='s=%r;print(s%%(s,round(%s*(1+5**.5)/2)))';print(s%(s,round(**2***(1+5**.5)/2)))

```

Try it online!
Uses the golden ratio to calculate the next number
> 5 votes

# Answer
# Jelly, 14 bytes

```
“×Øp+.ḞṭØv”Ṙv2

```

Try it online! or verify all required iterations.

### How it works

```
“×Øp+.ḞṭØv”Ṙv2  Main link. No arguments.

“×Øp+.ḞṭØv”     Set the left argument and return value to the string "×Øp+.ḞṭØv".
           Ṙ    Print a string representation of the return value and yield the
                unaltered return value.
            v2  Evaluate the return value as a Jelly program with left argument 2.
 ×Øp                Multiply the left argument by the golden ratio.
    +.              Add 0.5 to the resulting product.
      Ḟ             Floor; round the resulting sum down to the nearest integer.
        Øv          Yield the string "Øv".
       ṭ            Tack; append the result to the left to the result to the right.

```
> 4 votes

# Answer
# Swift, 251 bytes

A bit verbose for me, but I can't figure out how to get it shorter:

```
import Foundation;var n="\"";var u="\\";var s="import Foundation;var n=%@%@%@%@;var u=%@%@%@%@;var s=%@%@%@;print(String(format:s,n,u,n,n,n,u,u,n,n,s,n,(round(%f*(1+sqrt(5))/2))))";print(String(format:s,n,u,n,n,n,u,u,n,n,s,n,(round(2*(1+sqrt(5))/2))))

```

Ungolfed:

```
import Foundation
var n="\""
var u="\\"
var s="import Foundation;var n=%@%@%@%@;var u=%@%@%@%@;var s=%@%@%@;print(String(format:s,n,u,n,n,n,u,u,n,n,s,n,(round(%f*(1+sqrt(5))/2))))"
print(String(format:s,n,u,n,n,n,u,u,n,n,s,n,(round(2*(1+sqrt(5))/2))))

```

My trouble is trying to get the quotes around the new version of `s`.
> 1 votes

# Answer
# Javascript (ES6), 151 60 bytes

New version, credits to @Leaky Nun

```
x=i=>console.log('x='+x+';x('+(i*(5**.5+1)/2+.5|0)+')');x(2)

```

Old version :

```
x=i=>{var s=Math.sqrt(5),a=1;f=n=>{return Math.ceil((((1+s)/2)**n-((1-s)/2)**n)/s)};while(f(++a)<=i);console.log('x='+String(x)+';x('+f(a)+')');};x(2)

```

Based on this.
> 1 votes

# Answer
# Cheddar, 136 bytes

```
let b=1;for(let a=1;a<2;a=b-a){b+=a};let s='let b=1;for(let a=1;a<%i;a=b-a){b+=a};let s=%s;print s%b%@"39+s+@"39';print s%b%@"39+s+@"39

```

Try it online!
> 1 votes

# Answer
# dc, 35 bytes

```
2[r9k5v1+2/*.5+0k1/n91PP93P[dx]P]dx

```

A version with iteration (56 bytes):

```
2[rsP1dsN[lN+lNrsNdlP[s.q]s.=.lFx]dsFxlNn91PP93P[dx]P]dx

```
> 1 votes

# Answer
# Swift, 235 bytes

This is an improved version of Caleb's answer.

```
import Foundation;var n="\"",u="\\",s="import Foundation;var n=%@%@%@%@,u=%@%@%@%@,s=%@%@%@;print(String(format:s,n,u,n,n,n,u,u,n,n,s,n,(round(%f*(1+sqrt(5))/2))))";print(String(format:s,n,u,n,n,n,u,u,n,n,s,n,(round(2*(1+sqrt(5))/2))))

```
> 1 votes

# Answer
# Java (OpenJDK 8), 239 bytes

```
interface a{static void main(String[]p){int a=1,b=1;for(;a<2;a=b-a)b+=a;String s="interface a{static void main(String[]p){int a=1,b=1;for(;a<%d;a=b-a)b+=a;String s=%c%s%c;System.out.printf(s,b,34,s,34);}}";System.out.printf(s,b,34,s,34);}}

```

Try it online!
> 0 votes

---
Tags: code-golf, sequence, quine, fibonacci
---