title: Largest Product in MxN grid

text:
# Question
Title: Largest Product in MxN grid
Given an MxN grid of numbers, find the greatest product of a length 4 subsequence in any row, column, or diagonal. Subsequences *cannot* wrap around (e.g. `5 1 2 3` in the row `1 2 3 4 5`).

I/O can be anything reasonable: files, stdin/stdout, copy+pasting expressions/arguments, variables. (If I'm missing any esoteric I/O option, feel free to go ahead and post your solution anyways)

# Answer
> 1 votes
# J, 26 chars

```
>./,4*/\"1(,|:,]/.,]/.@|.)

```

Just an expression to which a rank 2 array could be appended.

`,|:,]/.,]/.@|.` takes the rank 2 array and concatenates 4 intermediate rank 2 arrays, the input's identity, transposition, and obliques, respectively. Here I feel like there's an uncomfortable amount of redundancy, because there are 2 `]`s, 3 `,`s, and 2 `/.`s... I can't think of a way to refactor those out.

`>./,4*/\"1` is just a straightforward maximum of each length 4 subsequence of each row of the newly made array, which of course corresponds to rows/columns/diagonals of the original.

# Answer
> 1 votes
# Mathematica 190

A 9x5 matrix.

```
m = RandomInteger[{1, 99}, {9, 5}];
m // MatrixForm

```

**Code** This produces the product and the factors.

```
{e, f} = Dimensions@m; z = Reverse; w = Flatten;
j = Join[m, n = m\[Transpose], p = z /@ m, q = z /@ n,
w[Table[Diagonal[#, k], {k, -(e - 4), f - 4}] & /@ {m, n, p, q}, 1]];
Sort[w[Partition[#, 4, 1] & /@ j, 1] /. {a_, b_, c_, d_} :> {a b c d, {a, b, c, d}}][[-1]]

```

> {37714500, {90, 85, 58, 85}}

---
Tags: code-golf
---


title: Bitwise Operators in Brainfuck

text:
# Question
Title: Bitwise Operators in Brainfuck
Your task is to create one brainfuck program for each of the following binary operators. Each program should take one or two 8-bit numbers (A and B) from input and calculate the specified operation:

1. `A XOR B`
2. `A AND B`
3. `A OR B`
4. `A Shifted Left by 1 (circular shift)`
5. `NOT A`

You do not have to implement all 5. Score is calculated by:

```
#totalCharacters + {4000 * #problemsNotCompleted}

```

So valid scores are from zero (best) to 20,000(nothing completed).

I don't care where you store the result, or whether or not you preserve the input. Assume 8-bit cells, and as many empty cells as you need to the right only.

You may assume the numbers are already in whatever memory location works best for you, so you don't need to worry about IO operations.

# Answer
## Score: 275

It works better to expand these with a binary counter. The less intuitive parts deal with the possibility that A or B is 0. I didn't find a profitable way to use nondestructive flow control in the actual bit manipulation of the first three. Incidentally these should all work fine with 16-bit cells and slowly with 32-bit.

**XOR, 86**

Assumes A and B are in cells 1 and 2, stores A XOR B in cell 2, pointer starts in cell 0 and ends in cell 5.

```
-[[>>>>>>[>>>]++[-<<<]<<<-]>]>>>[<]>[[>[>-<-]>[<<<<<<+>>>>>>[-]]>]+[<[<<<++>>>-]<<]>>]

```

**AND, 78**

Assumes A and B are in cells 1 and 2, stores A OR B in cell 4, pointer starts in cell 0 and ends in cell 5.

```
-[[>>>>>>[>>>]++[-<<<]<<<-]>]>>>[<]>[[>[>[<<<<+>>>>-]<-]>+>]<[<[<<<++>>>-]<<]]

```

**OR, 86**

Assumes A and B are in cells 1 and 2, stores A OR B in cell 2, pointer starts in cell 0 and ends in cell 5.

```
-[[>>>>>>[>>>]++[-<<<]<<<-]>]>>>[<]>[[>[>+<-]>[<<<<<<+>>>>>>[-]]>]+[<[<<<++>>>-]<<]>>]

```

**ROL, 18**

Assumes A is in cell 0, stores A ROL 1 in cell 1, pointer starts and ends in cell 0.

```
[>++[>>]<[>+>]<<-]

```

**NOT, 7**

Assumes A is in cell 0, stores NOT A in cell 1, pointer starts and ends in cell 0.

```
+[>-<-]

```
> 10 votes

# Answer
## Score: 686

All snippets assume that the numbers are already loaded in cell 0 and 1 and that the pointer points to cell 0. I can add an atoi snippet later if that's required for the challenge. For now, you can try the code like this:

```
+++++++++>    number 1
++++<         number 2

```

**XOR, 221**

Result is written to cell 10, pointer ends at cell 5

```
>>>>>++++++++[-<<<<<[->>+<<[->>->+<]>>[->>>>+<<]<<<<]>>>[-<<<+>>>]<<[->+<[->->+>
>>>>]>[->>>>>+>>]<<<<<<<<]>>[-<<+>>]>>>[->>+<<]>[>[-<->]<[->+<]]>[[-]<<<[->+>-<<
]>[-<+>]+>+++++++[-<[->>++<<]>>[-<<+>>]<]<[->>>>+<<<<]>>]<<<]

```

**AND, 209**

Result is written to cell 10, pointer ends at cell 5

```
>>>>>++++++++[-<<<<<[->>+<<[->>->+<]>>[->>>>+<<]<<<<]>>>[-<<<+>>>]<<[->+<[->->+>
>>>>]>[->>>>>+>>]<<<<<<<<]>>[-<<+>>]>>>[->[->+<]<]>[-]>[-<<<[->+>-<<]>[-<+>]+>++
+++++[-<[->>++<<]>>[-<<+>>]<]<[->>>>+<<<<]>>]<<<]

```

**OR, 211**

Result is written to cell 10, pointer ends at cell 5

```
>>>>>++++++++[-<<<<<[->>+<<[->>->+<]>>[->>>>+<<]<<<<]>>>[-<<<+>>>]<<[->+<[->->+>
>>>>]>[->>>>>+>>]<<<<<<<<]>>[-<<+>>]>>>[->>+<<]>[->+<]>[[-]<<<[->+>-<<]>[-<+>]+>
+++++++[-<[->>++<<]>>[-<<+>>]<]<[->>>>+<<<<]>>]<<<]

```

**Rotate Left, 38**

Result is written to cell 1, pointer ends at cell 4

```
[->++>+<[>-]>[->>+<]<<<]>>>>[-<<<+>>>]

```

**NOT, 7**

Result is written to cell 1, pointer ends at cell 0

```
+[+>+<]

```

## Explanation:

XOR, AND and OR all work in a similiar fashion: Calculate n/2 for each number and remember n mod 2. Calculate the logical XOR/AND/OR for the single bits. If the resulting bit is set, add 2^n to the result. Repeat that 8 times.

This is the memory layout I used:

```
 0      1        2        3      4        5         6        7
n1  |  n2  |  marker  |  n/2  |  0  |  counter  |  bit1  |  bit2  |

  8        9        10
temp  |  temp  |  result

```

Here's the source for XOR (numbers indicate where the pointer is at that time):

```
>>>>>
++++ ++++ counter
[
    -
    <<<<<

    divide n1 by two
    [ 0
        -
        >>+ set marker 2
        << 0
        [->>->+<] dec marker inc n/2
        >> 2 or 4
        [->>>>+<<]
        <<<<
    ]
    >>>
    [-<<<+>>>]
    <<

    divide n2 by two
    [ 1
        -
        >+ set marker 2
        < 1
        [->->+>>>>>] dec marker inc n/2
        > 2 or 9
        [->>>>>+>>]
        <<<< <<<<
    ]
    >>[-<<+>>] 3

    >>> 6

    [->>+<<]>[>[-<->]<[->+<]]>  one bit xor 8

    [
        [-]<<< 5
        [->+>-<<] copy counter negative
        > 6
        [-<+>]
        +> 7
        ++++ +++  cell 6 contains a one and cell 7 how many bits to shift
        [-<[->>++<<]>>[-<<+>>]<]  2^n
        < 6
        [->>>>+<<<<]
        >> 8
    ]

    <<<
]

```

For left rotate, once again there is a marker in cell 2 to determine if 2n is zero, since you can only determine if a cell is non-zero directly. If so, a carry bit is written to cell 4 and later added to 2n. This is the memory layout:

```
0      1        2       3       4
n  |  2n  |  marker  |  0  |  carry

```
> 8 votes

# Answer
## Score (current): 12038 837/-

The programs assume numbers are loaded in whatever cell is specified, by `,` or similar. It also assumes that all cells are 8-bit unsigned with wrapping as needed. At the start of each snippet, numbers are loaded at cell 0 (and 1 if needed).

### Bit operations - 799

The bit operations follow the same general structure.

```
Firstly, we define a divmod 2 (DM2) function.
CELLS:   A  B   C  D
INPUT:  *A  0   0  0
OUTPUT: *0 A/2 A%2 0
dp@A; while{
  dec A,2; inc B,1; dp@A; inc A,1
  while{ #Check if A was 1 at the start
    dec D,1; pour A,C; dp@A;
  }
  dec C,1; pour C,A; inc D,1; dp@D
  #If A was 1 at the start, D will be 1 here
  while{
    dec D,1; inc C,1; dec B,1; dp@D
  }
  dp@A
}
Translated into BF, we have
    [->+<[>>>-<<<[->>+<<]]>>-[<<+>>-]>+[-<+<->>]<<<]
I'm not that good at BF, so my algorithm may not be the smallest.

Next, we define the program.
In this, we assume that the numbers are loaded in $2 (cell 2) and $3.

inc $1,8; dp@1 {
  dec  $1
  pour $3,$6
  DM2  $2        # result in $3,$4
  DM2  $6        # result in $7,$8
  pour $7, $2
  pour $8,$5
  bop  $4,$5     # result in $6
  pour $1,$5
  pour $5,$4,$1
  down $4,$5     # decrease $4 till 0, decrease $5 by same amount
  inc  $5,#7
  shl  $6,$5
  pour $6,$0     # $0 is result
  dp@  1
}
#Now, the result is in $0

Translated to BF (with linebreaks for readability):
  >++++++++[
    ->>[->>>+<<<]<
    [->+<[>>>-<<<[->>+<<]]>>-[<<+>>-]>+[-<+<->>]<<<]>>>>  #DM2 $2
    [->+<[>>>-<<<[->>+<<]]>>-[<<+>>-]>+[-<+<->>]<<<]>     #DM2 $6
    [-<<<<<+>>>>>]>
    [-<<<+>>>]<<<<
    (bop)<<<
    [->>>>+<<<<]>>>>
    [<+<<<+>>>>-]<
    [->-<]>
    +++++++
    [->[-<<++>>]<<[->>+<<]>]
    [-<<<<<<+>>>>>>]
    <<<<<
  ]

Replace (bop) by the appropriate expression.

XOR works like this: (252-5+15=262)
  [->-<]>[[-]>+<]
AND works like this: (252-5+11=258)
  [>[>+<-]<-]
OR  works like this: (252-5+32=279)
  [->>>+<<<]>[->>+<<]>>[[-]<+>]<<<

So, combining these, we have a total of 262+258+279=799 D:

```

### Rotate Left A, 1 - 31/-

The number `A` is loaded in cell 0.

```
Pseudocode
    $0 := A
    $1 := $0 << 1    # this has the effect of discarding the top bit of A
    $2 := $0
    $3 := $0 << 1
    $2 -= $1 >> 1    # $2 now contains the top bit of A
    if $2 then $3++  # $3 now contains A rotated left 1
    res:= $3         # the result is in cell 3 now

Real code
    [->++>+>++<<<]>[-->-<]>[>+<[-]]
If you don't always need the pointer in the same position,
substitute [>+>] for the last loop (3 less chars).
However, the pointer will then sometimes end up in position 2, sometimes in position 4.

```

### NOT A - 7

The number `A` is loaded in cell 0.

```
Pseudocode
    $0  := A
    $0  += 1
    $1  := 256-$0   #since ~A=255-A
    res := $1

+[->-<]

```
> 3 votes

---
Tags: code-golf, binary, brainfuck
---


title: Obtaining ordering of cards

text:
# Question
Title: Obtaining ordering of cards
You are given a deck containing n cards. While holding the deck:

1. Take the top card off the deck and set it on the table
2. Take the next card off the top and put it on the bottom of the deck in your hand.
3. Continue steps 1 and 2 until all cards are on the table. This is a round.
4. Pick up the deck from the table and repeat steps 1-3 until the deck is in the original order.

Write a program to determine how many rounds it will take to put a deck back into the original order.

I found some answers online that had answers online for comparing and I cannot get the same answers. Either they are wrong or I am completely wrong. I went through a few examples of my own got these answers:

5 cards: order: 12345

```
1: 24531
2: 43152
3: 35214
4: 51423
5: 12345   <-- 5 rounds

```

6 cards:

order: 123456

```
1: 462531
2: 516324
3: 341265
4: 254613
5: 635142
6: 123456   <-- 6 rounds

```

Answers I found online were:

Problem: http://www.velocityreviews.com/forums/t641157-solution-needed-urgent.html

```
Answer: http://www.velocityreviews.com/forums/t641157-p2-solution-needed-urgent.html   <-- last post

```

I found another solution that has the same solution as mine but not sure on any solutions credibility:

```
http://entrepidea.com/algorithm/algo/shuffleCards.pdf

```

I was wondering if anyone has done this problem before and would be able to confirm which answers are correct. I need something to test against to see if my program is giving the correct output. THANKS!

# Answer
> 2 votes
# Python

```
def game(a):
    deck = range(1,a+1)
    #store the deck
    origDeck = []
    #copy the deck
    origDeck.extend(deck)
    table =[]
    ans = 0
    while 1:
        while len(deck) > 0:
            table.append(deck.pop(0))
            if len(deck) == 0:
                break
            deck.append(deck.pop(0))
        table.reverse()
        deck,table=table,deck
        ans+=1
        #this is the condition that exits the infinite loop
        if deck==origDeck:
            break
    print ans

```

Calling `game(n)` prints the number of rounds for n cards. The code can be easily changed to allow for printing the deck between rounds (add `print deck` before `if deck==origDeck`).

---

Tests (1 through 50):

```
1: 1
2: 2
3: 3
4: 2
5: 5
6: 6
7: 5
8: 4
9: 6
10: 6
11: 15
12: 12
13: 12
14: 30
15: 15
16: 4
17: 17
18: 18
19: 10
20: 20
21: 21
22: 14
23: 24
24: 90
25: 63
26: 26
27: 27
28: 18
29: 66
30: 12
31: 210
32: 12
33: 33
34: 90
35: 35
36: 30
37: 110
38: 120
39: 120
40: 26
41: 41
42: 42
43: 105
44: 30
45: 45
46: 30
47: 60
48: 48
49: 120
50: 50

```

31 produces a peculiar output; it goes through 210 rounds.

It appears that primes have large cycles. For example, 97 has the largest cycle under 100: 6435.

# Answer
> 1 votes
## Haskell

The way of handling cards is somewhat problematic, the code for `turn` became rather complex. But finally both the cases for 5 and 6 match.

```
import Data.List
import Control.Arrow

spl :: [a] -> ([a],[a])
spl = (map snd***map snd) . partition ((==1).(`mod`2).fst) . zip [1..]

turn :: [a] -> [a]
turn' :: [a] -> [a] -> [a]
turn x = reverse $ turn' x []
turn' [] []       = []
turn' [] ls       = turn' (reverse ls) []
turn' [x] []      = [x]
turn' [x] ls      = turn' (x:(reverse ls)) []
turn' (x:y:ys) ls = x : (turn' ys (y:ls))

cardCycle x = first : (takeWhile (/=first) $ iterate turn (turn first))
  where first = [1..x]

ans = length . cardCycle

main = mapM_ (\x -> putStrLn ((show x) ++ ": " ++ (show (ans x)))) [1..20]

```

.

```
1: 1
2: 2
3: 3
4: 2
5: 5
6: 6
7: 5
8: 4
9: 6
10: 6
11: 15
12: 12
13: 12
14: 30
15: 15
16: 4
17: 17
18: 18
19: 10
20: 20

```

16 seems to be an interesting one so here's the cycle (layout added):

```
> cardCycle 16
[[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
,[16,8,12,4,14,10,6,2,15,13,11,9,7,5,3,1]
,[1,2,9,4,5,13,10,8,3,7,11,15,6,14,12,16]
,[16,8,15,4,14,7,13,2,12,6,11,3,10,5,9,1]]

```

# Answer
> 1 votes
# Pure Bash

It is not clear in your question (unless I missed it) if when you put a card on the table you put it *above* or *below* the cards already there. Here are two versions, and you'll see that the answer differs:

## Cards above

```
orig="12345"
deck=$orig
table=

nb=0

play() {
    ((++nb))
    while [[ -n $deck ]]; do table=${deck:0:1}$table; deck=${deck:2}${deck:1:1}; done
    deck=$table
    table=
    echo "$nb: $deck"
}

while ((nb==0)) || [[ $deck != $orig ]]; do play; done

```

this yields:

```
1: 24531
2: 43152
3: 35214
4: 51423
5: 12345

```

## Cards below

Replace `play` with:

```
play() {
    ((++nb))
    while [[ -n $deck ]]; do table+=${deck:0:1}; deck=${deck:2}${deck:1:1}; done
    deck=$table
    table=
    echo "$nb: $deck"
}

```

which yields:

```
1: 13542
2: 15243
3: 12345

```

## Golfed versions, reading input on stdin

* Below:

```
read o;d=$o;t=;n=0;p(){((++n));while [[ $d ]];do t+=${d:0:1};d=${d:2}${d:1:1};done;d=$t;t=;echo $d;[[ $d = $o ]]||p; };p;echo $n

```
* Above:

```
read o;d=$o;t=;n=0;p(){((++n));while [[ $d ]];do t=${d:0:1}$t;d=${d:2}${d:1:1};done;d=$t;t=;echo $d;[[ $d = $o ]]||p; };p;echo $n

```

# Answer
> 1 votes
# Mathematica

`shuffleTillUnshuffled[
 n]` takes a deck of n cards and shuffles it until it returns to the original order.

`playRound` takes a deck and returns the reordered deck of cards after one round of shuffling.

`rule1` places the top card on the table and the second card at the bottom of the deck.

`rule2` places the last card of the deck onto the table.

`[[2]]`, that is, `Part[{inHand,onTable},2]` removes the deck from the table so that it can be used, if still unordered, in the next round.

```
rule1={{s_,m1_,e___},{l___}}:> {{e,m1},{s,l}};
rule2={{s_},{e__}}:> {{},{s,e}};
playRound[deck_]:=({deck,{}}//.{rule1,rule2})[[2]]
shuffleTillUnshuffled[nCards_]:=  {rr=RotateRight[NestWhileList[playRound[#]&,playRound@Range@nCards,!OrderedQ[#]&]];
"Deck size: "<>ToString@nCards<>" cards; Rounds: "<>ToString@Length[rr],rr//Grid}

shuffleTillUnshuffled[4]
shuffleTillUnshuffled[5]
shuffleTillUnshuffled[13]

```

---
Tags: permutations
---


title: Fastest Sort in BrainF***

text:
# Question
Title: Fastest Sort in BrainF***
After having implemented QuickSort in BrainF\***, I realized it probably wasn't that quick. Operations that are O(1) in normal languages (like array indexing) are significantly longer in BF. Most of the rules for what makes an efficient sort can be thrown out the window when you are coding in a Turing tarpit.

So here is a challenge to implement the "Fastest BrainF\*** Sort Routine Ever". I will time all entries using the interpreter below. The intepreter uses a 16K tape of unsigned characters. Both the tape and the cells wrap when advanced/incremented past the limits. Reading the EOF puts a 0 in the current cell. The measured time includes both the time to parse the source file and the time to process all input files. Fastest code wins.

The test vector will be a set of Ascii files designed to test sorting edge cases, including

* An already sorted list: "ordered"

```
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

```
* A reverse sorted list: "reverse"

```
~}|{zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)('&%$#"!

```
* A file consisting of many copies of a few unique values: "onlynine"

```
ibbkninbkrauickabcufrfckbfikfbbakninfaafafbikuccbariauaibiraacbfkfnbbibknkbfankbbunfruarrnrrrbrniaanfbruiicbuiniakuuiubbknanncbuanbcbcfifuiffbcbckikkfcufkkbbakankffikkkbnfnbncbacbfnaauurfrncuckkrfnufkribnfbcfbkbcrkriukncfrcnuirccbbcuaaifiannarcrnfrbarbiuk

```
* A completely random ascii file: "random"

```
'fQ`0R0gssT)70O>tP[2{9' 0.HMyTjW7-!SyJQ3]gsccR'UDrnOEK~ca 'KnqrgA3i4dRR8g.'JbjR;D67sVOPllHe,&VG"HDY_'Wi"ra?n.5nWrQ6Mac;&}~T_AepeUk{:Fwl%0`FI8#h]J/Cty-;qluRwk|S U$^|mI|D0\^- csLp~`VM;cPgIT\m\(jOdRQu#a,aGI?TeyY^*"][E-/S"KdWEQ,P<)$:e[_.`V0:fpI zL"GMhao$C4?*x

```
* A random file over the range 1..255: "wholerange"

```
öè—@œ™S±ü¼ÓuÇ¯ŠfÎ€n‚ZÊ,ˆÖÄCítÚDý^öhfF†¬I÷xxÖ÷GààuÈ©ÈÑdàu.y×€ôã…ìcÑ–:*‰˜IP¥©9Ä¢¬]Š\3*\®ªZP!YFõ®ÊÖžáîÓ¹PŸ—wNì/S=Ìœ'g°Ì²¬½ÕQ¹ÀpbWÓ³
»y  »ïløó„9k–ƒ~ÕfnšÂt|Srvì^%ÛÀâû¯WWDs‰sç2e£+PÆ@½ã”^$f˜¦Kí•òâ¨÷ žøÇÖ¼$NƒRMÉE‹G´QO¨©l¬k¦Ó

```

Each input file has at most 255 bytes.

Here is the interpreter. It's written for console-mode Windows, but should be easy to port: just replace `read_time()` and `sysTime_to_ms()` with platform-specific equivalents.
Usage: `bftime program.bf infile1 [infile2 ...]`

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

#define MS_PER_SEC  1000.0f
#define MAXSIZE  (0x4000)
#define MAXMASK  (MAXSIZE-1)

typedef  __int64 sysTime_t;
typedef unsigned char Uint8;
typedef unsigned short Uint16;

typedef struct instruction_t {
   Uint8 inst;
   Uint16 pair;
} Instruction;

Instruction prog[MAXSIZE] = {0};
Uint8 data[MAXSIZE] = {0};
const Uint8 FEND = EOF;

sysTime_t read_time() {
    __int64 counts;
    QueryPerformanceCounter((LARGE_INTEGER*)&counts);
    return counts;
}

float sysTime_to_ms(sysTime_t timeIn) {
    __int64 countsPerSec;
    QueryPerformanceFrequency((LARGE_INTEGER*)&countsPerSec);
    return (float)timeIn * MS_PER_SEC / (float)countsPerSec;
}

int main(int argc, char* argv[])
{
   FILE* fp;
   Uint8 c;
   Uint16 i = 0;
   Uint16 stack = 0;
   sysTime_t start_time;
   sysTime_t elapsed=0,delta;

   if (argc<3) exit(printf("Error: Not Enough Arguments\n"));
   fp = fopen(argv[1],"r");
   if (!fp) exit(printf("Error: Can't Open program File %s\n",argv[1]));

   start_time=read_time();
   while (FEND != (c = fgetc(fp)) && i <MAXSIZE) {
      switch (c)  {
      case '+': case '-': case ',': case '.': case '>': case '<':
         prog[++i].inst = c;
         break;
      case '[':
         prog[++i].inst = c;
         prog[i].pair=stack;
         stack = i;
         break;
      case ']':
         if (!stack) exit(printf("Unbalanced ']' at %d\n",i));
         prog[++i].inst = c;
         prog[i].pair=stack;
         stack = prog[stack].pair;
         prog[prog[i].pair].pair=i;
         break;
      }
   }
   if (stack) exit(printf("Unbalanced '[' at %d\n",stack));
   elapsed = delta = read_time()-start_time;
   printf("Parse Time: %f ms\n", sysTime_to_ms(delta));

   for (stack=2;stack<argc;stack++) {
      Instruction *ip = prog;
      fp = fopen(argv[stack],"r");
      if (!fp) exit(printf("Can't Open input File %s\n",argv[stack]));
      printf("Processing %s:\n", argv[stack]);
      memset(data,i=0,sizeof(data));

      start_time=read_time();
      //Run the program
      while (delta) {
         switch ((++ip)->inst) {
         case '+': data[i]++; break;
         case '-': data[i]--; break;
         case ',': c=getc(fp);data[i]=(FEND==c)?0:c; break;
         case '.': putchar(data[i]);  break;
         case '>': i=(i+1)&MAXMASK;   break;
         case '<': i=(i-1)&MAXMASK;   break;
         case '[': if (!data[i]) ip = prog+ip->pair; break;
         case ']': if (data[i])  ip = prog+ip->pair;  break;
         case 0: delta=0; break;
         }
      }
      delta = read_time()-start_time;
      elapsed+=delta;
      printf("\nProcessing Time: %f ms\n", sysTime_to_ms(delta));
   }
   printf("\nTotal Time for %d files: %f ms\n", argc-2, sysTime_to_ms(elapsed));
}

```

---

**Results So Far**

Here's the average time of 5 runs of the complete set of vectors:

```
 Author    Program      Average Time    Best Set          Worst Set
 AShelly   Quicksort    3224.4 ms       reverse (158.6)   onlynine (1622.4)
 K.Randall Counting     3162.9 ms       reverse (320.6)   onlynine  (920.1)
 AShelly   Coinsort      517.6 ms       reverse  (54.0)   onlynine  (178.5)
 K.Randall CountingV2    267.8 ms       reverse  (41.6)   random     (70.5)
 AShelly   Strandsort    242.3 ms       reverse  (35.2)   random     (81.0)

```

# Answer
> 10 votes
```
>>+>,[->+>,]<[<[<<]<[.<[<<]<]>>[+>->]<<]

```

I don't remember whose idea this algorithm was. Maybe Bertram Felgenhauer's? It came from discussions around Brainfuck Golf contest #2, over a decade ago.

This is the fastest one yet on the sample inputs.

It's also not limited to inputs of length \<256, but can handle arbitrarily long inputs.

Both these things were also true of Albert's answers, below. The nice thing about this one is that the running time is O(N) in the input length. Yes, this thing actually runs in linear time. It already ate a constant factor of 255 as a snack.

# Answer
> 9 votes
Here's a sort that is at least 6x faster than my quicksort. It's an algorithm that would make little sense in a traditional language, since it's O(N\*m) where m is the maximum input value. After collecting the input, it passes through the array, counting cells \> 0 and then decrementing each one. It then adds 1 to the first `count` cells in the result vector. It repeats the passes until the count is 0.
BF:

```
Get Input
>,[>>+>,]
Count values GT 0 and decrement each
<[<[<<<+>>>-]<[-<<+>>>]>[<]<<]
While count: add 1 to results
<[[[<<+>>-]<+<-]
Seek back to end of input
>[>>]>>>[>>>]
Repeat counting step
<<<[<[<<<+>>>-]<[-<<+>>>]>[<]<<]<]
Seek to far end of results and print in reverse order
<[<<]>>[.>>]

```

C equivalent algorithm:

```
 uchar A[MAX]={0}; uchar R[MAX]={0}; int count,i,n=0;
 while (A[n++]=getchar()) ;
 do {
   count = 0;
   for (i=0; i<n; i++) count += (A[i]) ? (A[i]-->0) : 0;
   for (i=0; i<count; i++) R[i]++;
 } while (count>0);
 for (i=0; R[i]; i++) ;
 for (i--; i>=0; i--) putchar(R[i]);

```

---

Here's one that's 2x as fast. It's based loosely on "spaghetti sort": it lays down a string of 1s as long as each input. The value in each cell represents the number of strands at least that long. (So \[3,2,1,2\] becomes `|4|0|3|0|1|0|0|`). Then it starts 'measuring' the strands and prints out the length every time it finds the end of one.

```
>,[ [-[>>+<<-]>+>] <[<<]>,]   build strand of 1s for each input
+>[>+<-]>[                    while there are strands
  >[>+<<->-]                  do any strands end here?
  <[<<.>>-]                   print length of all that do
  <<[>>+<<-]>>+>>]            shift right 1; inc length

```

Raw:

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

```

# Answer
> 3 votes
A simple counting sort implementation. Each bucket is 3 cells wide, containing the current input, a marker, and the count of the number of times the counter appears in the input.

```
process input
,[

while input is not zero
[

decrement input
-

copy input over to next bucket
[->>>+<<<]

mark next bucket as not the first
>>>>+<

repeat until input is zero
]

increment count for this bucket
>>+

rewind using markers
<[-<<<]<

process next input
,]

generate output
>+[>[<-.+>-]<[->>>+<<<]>>>+]

```

without comments:

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

```

# Answer
> 3 votes
```
>,[>+>,]+[<[<-<]>>[<[>>]>[<->[>>]<.<[<<]]>>]<<<<<+]

```

# Answer
> 3 votes
```
>>+>,[>+>,]<[[<-<]>+>+[>]>[[-<<[[>>+<<-]<]>>]>-.+[>]>]<<]

```

---
Tags: fastest-code, brainfuck
---


title: Finding nCr for code-golf

text:
# Question
Title: Finding nCr for code-golf
The problem is to compute nCr = n!/(r!) * (n-r)! in the fewest characters possible. The input will be in the form: 1st line will have number of test cases and second line will have n and r for each testcase. You need to print ncr

e.g.

```
Input
1
100 10

Output:
17310309456440

```

Here's what I have in python. Is there a way to reduce the number of characters further ?\[143 chars presently\]

```
r=raw_input
f=lambda x:0**x or x*f(x-1)
C=lambda n,r:f(n)/f(r)/f(n-r)
for i in range(int(r())):print C(*map(int, r().split()))

```

Thanks!

# Answer
> 0 votes
# Python 3 (100 chars)

```
I=input
C=lambda n,r:r and C(n-1,r-1)*n//r or 1
for _ in' '*int(I()):print(C(*map(int,I().split())))

```

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


title: TUT language translator

text:
# Question
Title: TUT language translator
Text may be translated to a written version of TUT language by replacing each letter by the corresponding "TUT word", as given in the following table (adapted from the linked article)<sup>*</sup>:

```
a  e        h  hash     o  o        u  yu
b  bub      i  ay       p  pup      v  vuv
c  kut      j  jag      q  kwak     w  waks
d  dud      k  kak      r  rut      x  eks
e  i        l  lul      s  sus      y  yak
f  fuf      m  mum      t  tut      z  zuz
g  jug      n  nun

* Exceptions:
(1) Upper case letters have corresponding TUT words in upper case.
(2) A doubled letter becomes 'skwer' ('SKWER') followed by the TUT word for that letter.
    - An n-fold letter is treated as a number of doubles, followed by a single if needed.
    - To be considered a double or n-fold letter, the letters must be in the same case.
(3) 'rut' ('RUT') is replaced by 'rud' ('RUD') if immediately followed by 'dud' ('DUD').

```

Write a program with the following i/o behavior:

**Input** (from stdin): A binary (0/1) indicator *i* and an ASCII string *s*.

* If *i* = 0 then *s* may contain any ASCII text.
* If *i* = 1 then *s* must be the TUT Language output for some valid input.

**Output** (to stdout): A binary (0/1) indicator *j* and an ASCII string *t*.

* If *i* = 0 then *j* = 1 and *t* is the translation of *s* **to** TUT Language.
* If *i* = 1 then *j* = 0 and *t* is the translation of *s* **from** TUT Language.
* For any valid input, applying the program to its own output must exactly reproduce the original input; i.e., *program* (*program* (*i*, *s*)) = (*i*, *s*). Input and output must have exactly the same format.

**Scoring**: The score is the number of characters in the program -- lowest score wins.

**Examples**

**(a)**

```
(0, 'Look for the birds.')
(1, 'LULskwerokak fuforut tuthashi bubayruddudsus.')

```

**(b)**

```
(0, '"Mrs. Hogwallop up and R-U-N-N-O-F-T."')
(1, '"MUMrutsus. HASHojugwakseskwerlulopup yupup enundud RUT-YU-NUN-NUN-O-FUF-TUT."')

```

(**c**)

```
(0, 'QWX WWW Rrrrd deeeeep')
(1, 'KWAKWAKSEKS SKWERWAKSWAKS RUTskwerrutruddud dudskweriskweriipup')

```

(**d**)

```
(0, 'aa AA aA Aa rd RD rD Rd')
(1, 'skwere SKWERE eE Ee ruddud RUDDUD rutDUD RUTdud)

```

(((Aside about pronunciation: The TUT words for the vowels (`e`, `i`, `ay`, `o`, `yu`) are supposed to represent the usual sounds of (a, e, i, o, u) when reciting the alphabet -- i.e., rhyming with (may, me, my, mow, mew). In the three-or-more-letter TUT words, the symbols (`u`,`a`,`e`) are supposed to sound as in (but, bat, bet) respectively -- these are ASCII replacements for (`ʌ` `æ` `ɛ`) in the linked article.)))

# Answer
> 6 votes
### Ruby, ~~310~~ 311 characters

```
h=Hash[(?a..?z).zip %w{e bub kut dud i fuf jug hash ay jag kak lul mum nun o pup kwak rut sus tut yu vuv waks eks yak zuz}]
h["rd"]="ruddud"
h.keys.each{|k|h[k[0]+k]="skwer"+h[k]}
h.keys.each{|k|h[k.upcase]=h[k].upcase}
h=h.invert if b=getc==?1
i=gets
print b ?0:1;(k=i;k=k.chop until h[k]||!k[1];$><<(h[k]||k);i[k]="")until i==""

```

Correctly handles:

* squared uppercase (unfix by merging iterations gains 18 characters)
    + if `AA` should turn into `skwerE`, swap lines #3 and #4
    + I also assume `aA` and `Aa` should turn into `eE` and `Ee` respectively
* `rrd` translates to \`skwerruddud (unfix gains 3 characters)
* in cubes the first pair is reported as a square. `rrrd` turns into `skwerrutruddud`. `rrrrd` becomes `skwerrutskwerruddud`
* the output is now a valid input. It is, indeed, required by the spec
* uses newline as input terminator

~~Input requires there be no newline between the indicator and the string, output puts it there (fix: 1 character).~~ Console output suppressed at this point to prevent mixing with STDIN. Unfix free, it's just a little bit uglier.

Example input:

```
0Hello

```

Output:

```
1
HASHiskwerlulo

```

# Answer
> 3 votes
## Perl, ~~453~~ ~~443~~ ~~309~~ ~~307~~ ~~303~~ 299

```
($x,$_)=split//,<>,2;@x{a..z,rd}=(e,bub,kut,dud,i,fuf,jug,hash,ay,jag,kak,lul,mum,nun,o,pup,kwak,rut,sus,tut,yu,vuv,waks,eks,yak,zuz,ruddud);$x{$_ x2}=skwer.$x{$_}for a..z;$x{uc$_}=uc$x{$_}for keys%x;%x=reverse%x if$x;$z=join"|",sort{length$b<=>length$a}keys%x;s/\G(.*?)($z)/$1$x{$2}/g;print!$x+0,$_

```

**Test cases:**

I have tested successfully the (a),(b),(c) and (d) test cases provided in the OP.

**A \*somewhat\* more readable version:**

```
($x,$_)=split//,<>,2;
@x{a..z,rd}=(e,bub,kut,dud,i,fuf,jug,hash,ay,jag,kak,lul,mum,nun,o,pup,kwak,rut,sus,tut,yu,vuv,waks,eks,yak,zuz,ruddud);
$x{$_ x2}=skwer.$x{$_}for a..z;
$x{uc$_}=uc$x{$_}for keys%x;
%x=reverse%x if$x;
$z=join"|",sort{length$b<=>length$a}keys%x;
s/\G(.*?)($z)/$1$x{$2}/g;
print!$x+0,$_

```

# Answer
> 2 votes
## Tcl, ~~395~~ ~~394~~ 392

```
set m { rd ruddud a e h hash o o u yu b bub i ay p pup v vuv c kut j jag q kwak w waks d dud k kak r rut x eks e i l lul s sus y yak f fuf m mum t tut z zuz g jug n nun ঙ skwer}
set m $m[string tou $m]
if [read stdin 1] {puts 0[regsub -all ঙ(.) [string map [lreverse $m] [gets stdin]] {\1\1}]} {puts 1[string map $m [regsub -all (.)\\1 [gets stdin] ঙ\\1]]}

```

Notes:

* Uses `skwerruddud` for `rrd`.
* `skwereskweree` for `aaaaa`.

Example input:

```
0Hello

```

Output:

```
1HASHiskwerlulo

```

How it works:

* `m` is at the beginning a string.
* I concatiate it with the uppercase map.
* \[string map\] does most of the stuff for me (uses a list, so anything that is a valid list...)
* regexp for for the double characters. Use a special replacement character ().

# Answer
> 2 votes
## Perl 385

```
$t=e0bub0kut0dud0i0fuf0jug0hash0ay0jag0kak0lul0mum0nun0o0pup0kwak0rut0sus0tut0yu0vuv0waks0eks0yak0zuz;@t=split 0,$t."0\U$t";@s=(a..z,A..Z);while(<>){($-,$_)=split/ /,$_,2;@l{$-?@t:@s}=$-?@s:@t;if($-){for$@(@t){s/skwer$@/$@$@/gi}for$@(@t){s/$@/$l{$@}/g}s/(r)ud/$1/gi}else{s/(.)/$l{$1}||$1/ge;for$@(@t){$r=lc$@eq$@?"skwer":"SKWER";s/$@$@/$r$@/g}s/(ru)t(d)/$1$2$2/gi}$-=!$-;print"$- $_"}

```

Syntax highlighter hates this one...

Expects input on STDIN, format is `0 (or 1) String to convert here.`:

```
0 Hello! # input
1 HASHiskwerlulo! # output

1 HASHiskwerlulo!
0 Hello!

0 Look for the birds.
1 LULskwerokak fuforut tuthashi bubayruddudsus.

1 LULskwerokak fuforut tuthashi bubayruddudsus.
0 Look for the birds.

0 "Mrs. Hogwallop up and R-U-N-N-O-F-T."
1 "MUMrutsus. HASHojugwaksaskwerlulopup yupup anundud RUT-YU-NUN-NUN-O-FUF-TUT."

1 "MUMrutsus. HASHojugwaksaskwerlulopup yupup anundud RUT-YU-NUN-NUN-O-FUF-TUT."
0 "Mrs. Hogwallop up and R-U-N-N-O-F-T."

```

**Edit**: I've noticed an issue with the translation of X (it becomes 'aks' in the reversion, I'll look into this later. Might need to re-order the hash :(.

# Answer
> 2 votes
## APL (Dyalog) (372)

You can really tell APL doesn't have built-in string handling functions (except for the generic array ones). I had to write my own `tolower` (it's `L`). As always with multiline Dyalog APL, to test it, paste it in an edit window and then call it (`T`).

```
T
Q←⎕UCS
L←{Q(Q⍵)+32×⍵∊⎕A}
Z←{⎕←⊃z,.⍺⍺1⌽z←⍵,' '}
w←L¨W←1↓¨W⊂⍨' '=W←' E BUB KUT DUD I FUF JUG HASH AY JAG KAK LUL MUM NUN O PUP KWAK RUT SUS TUT YU VUV WAKS EKS YAK ZUZ RUD SKWER'
⍞{⎕←~⍵:{U←L⍣(l←⍺∊L⎕A)
~l∨⍺∊⎕A:⍺
⍺=⍵:U⊃⌽W
'rd'≡L¨⍺⍵:U'RUD'
U⊃W[96-⍨Q+L⍺]}Z⍺
{'rR'∊⍨v←⊃⍺:v
(⊃⌽w)≡m←L⍺:⍵∇⍬
~w∊⍨⊂m:⍺
L⍣(⍺≡L⍺)⍨⎕A/⍨26↑≡∘m¨w}Z{~×⍴⍵:''
∨/H←⊃¨⍷∘(L⍵)¨w:(⊂l↑⍵),∇⍵↓⍨l←⍴⊃H/W
(⊂⊃⍵),∇1↓⍵}⍺}⎕

```

Usage:

```
      T
⎕:
0
"Mrs. Hogwallop up and R-U-N-N-O-F-T."
1
"MUMrutsus. HASHojugwakseskwerlulopup yupup enundud RUT-YU-NUN-NUN-O-FUF-TUT."
      T
⎕:
1
"MUMrutsus. HASHojugwakseskwerlulopup yupup enundud RUT-YU-NUN-NUN-O-FUF-TUT."
0
"Mrs. Hogwallop up and R-U-N-N-O-F-T."

```

# Answer
> 2 votes
## GNU Sed, 514

```
s/$/\n@a!e@b!bub@c!kut@d!dud@e!i@f!fuf@g!jug@h!hash@i!ay@k!kak@l!lul@m!mum@n!nun@o!o@p!pup@q!kwak@r!rud@r!rut@s!sus@t!tut@u!yu@v!vuv@w!waks@x!eks@y!yak@z!zuz/
s/.*\n\(.*\)/&\U\1@/
ta
:a
s/^1/0\v/
td
s/^0/1\v/
:t
/\v\n/bf
s/\v\([^a-z]\)/\1\v/i
tt
s/\v\([a-z]\)\1/skwer\v\1/
s/\v\([A-Z]\)\1/SKWER\v\1/
s/\v\(.*\)\(.*\n.*@\1!\(\w\+\)@\)/\3\v\2/
s/rut\vd/rud\vd/
s/RUT\vD/RUD\vD/
bt
:d
/\v\n/bf
s/\v\([^a-z]\)/\1\v/i
td
s/\v\(skwer\)/\1\v/i
s/\v\(.*\)\(.*\n.*@\(.\)!\1@\)/\3\v\2/
s/skwer\(.\)\v/\1\1\v/
bd
:f
s/\v.*//

```

Could probably be shortened, though I'm done for now.

Uses a lookup table to handle conversions in both directions, should handle all exceptions including skwer case and ruddud/RUDDUD correctly.

input taken on each line as 0/1 followed by the string. Uses `\v` (vertical tab) as a cursor.

---
Tags: code-golf, string
---


# Question
Title: Build a solver for the "N balls on a scale" problem
The twelve-balls problem is a famous problem where you are given twelve balls, one of which is a different weight, but you don't know whether it is heavier or lighter than the other balls. Using only three weighings of a two-sided scale, it is possible to find the differently weighted ball, *and* determine whether it is heavier or lighter.

Your task is to build a program that does the following:

* Accept a number of balls `N` to be compared, from `8` to `100`. (In the traditional problem, `N = 12`.)
* Produce two lists of numbers, representing the balls to be placed on each side of the balance. An equal number of balls must be placed on each side.
* Accept an input signifying whether the left side of the scale is heavier, the right side is heavier, or the two sides are equal (this can be represented any way you want to: e.g. `-1` for left, `0` for equal, `1` for right, or `1` for left, `2` for right, and `3` for equal), and in response, either produce another pair of lists of balls to be weighed, or a guess as to which ball is the different one and whether it is heavier or lighter.

Your score is the sum of the *maximum* number of weighings for each value of `N` from `8` to `100` that it took to figure out the right answer for `N` balls using your algorithm (each case of "ball `x` is heavier/lighter" must be tested). Lowest score wins.

For example, if for `N = 12`, your algorithm managed to get 3 weighings for every case except "ball 8 is heavy" where it took 4 weighings, your score for `N = 12` is 4. If your maximum score was 10 weighings for each `N` from 8 to 100, your final score would be `930`.

Your algorithm must return the correct answer for all possible test cases (for any `N`, there are `2N` possible test cases, which is a total of 10,044). In addition, the source code of your solution may not exceed 51,200 bytes (50 KB) in size.

# Answer
## Tcl, ~~455~~ 426

```
proc weight n {
   set num [expr {int(log($n*2-1)/log(3))+1}]
   set len [expr {$n/3}]
   set pn 0
   set pri {2 5 7 11 13 17 19 23 29 31 37 41 43 59 61 67}
   for {set i 0} {$i < $num} {incr i} {
       set a {}
       while {![llength $a]} {
           set a {}
           set b {}
           set c {}
           while {
               ($n+1)%[lindex $pri $pn]==0
             ||($n-1)%[lindex $pri $pn]==0
             ||$n%[lindex $pri $pn]==0} {incr pn; puts $pn}
           set cpn [lindex $pri $pn]
           for {set j 0} {$j < $len} {incr j} {
               set tmp [expr {($j*$cpn)%$n}]
               lappend a $tmp
               incr tmp 1
               if {$tmp in $a} {set a {}; break}
               lappend b $tmp
           }
           incr pn
       }
       for {set j 0} {$j < $n} {incr j} {
           if {$j ni $a && $j ni $b} {lappend c $j}
       }
       puts "[lsort -integer $a] VS [lsort -integer $b] - Which is havier? -1 = left, 0 = equal, 1 = right"
       set idx [expr {[gets stdin] + 1}]
       if {$i == 0} {
           if {$idx == 1} {
               set p1 $c
               set p2 $c
           } elseif {$idx == 0} {
               set p1 $a
               set p2 $b
           } else {
               set p1 $b
               set p2 $a
           }
       } else {
           set lists [list $a $c $b]
           set p1 [lmap it [lindex $lists $idx] {if {$it ni $p1} continue; set it}]
           set p2 [lmap it [lindex $lists 2-$idx] {if {$it ni $p2} continue; set it}]
       }
   }
   if {[llength $p1]} {puts "Result $p1"} {puts "Result $p2"}
}
puts "Number of balls?"
weight [gets stdin]

```

No matter what you choose, the next question is always the same.
> 1 votes

# Answer
# Python - 4929 weighings

A sketch of a trivial, last-place solution:

```
N = input("Enter number of balls: ")
a = 1
b = 2

print a, "|", b
first_result = input("Is left side heavy (1), right side heavy (2), or both equal (3)? ")

while(True):
    b += 1
    print a, "|", b
    result = input("Is left side heavy (1), right side heavy (2), or both equal (3)?")
    if result == first_result and result != 3:
        # ball 1 is our culprit.
        print "Ball 1 is %s." % ("heavier" if first_result == 1 else "lighter")
        break
    elif result != first_result and result == 3:
        # ball 2 is our culprit.
        print "Ball 2 is %s." % ("heavier" if first_result == 2 else "lighter")
        break
    elif result != first_result and first_result == 3:
        # ball b is our culprit.
        print "Ball %d is %s." % (b, "heavier" if result == 2 else "lighter")
        break

```

This solution simply continuously puts the first ball on the left side and a different ball on the right side, until it's found out that either the first ball is of a different weight, or one of the others is.

This takes a maximum of `N-1` weighings for `N` balls (in any case where the last ball is the different one, `N-1` weighings are required), which is 4929 weighings total.
> 0 votes

# Answer
## Tcl, 369

```
proc weight balls {
    if {[llength $balls] == 1 || [llength $balls] == 0} {return [lindex $balls 0]}
    set len [expr {([llength $balls]+1)/3}]
    set a [lrange $balls 0 ${len}-1]
    set b [lrange $balls $len [expr {$len*2-1}]]
    set c [lrange $balls [expr {$len*2}] end]
    puts "$a VS $b (0 = left side is havier, 1 = right side is havier, 2 = equal)"
    tailcall weight [lindex [list $a $b $c] [gets stdin]]
}
puts "Number of balls"
for {set i 1} \$i<=[gets stdin] {incr i} {lappend balls $i}
puts [weight $balls]

```

The algorithm is very simple: (try to) split the list in 3 equal parts (last can be different), weight the first 2, and do that again for the selected part (if equal, use the 3rd part)
> 0 votes

# Answer
# Python - ?

```
#recursive weighing method
def weigh(list, heavy):
    l=len(list)
    if l==1:
        return list[0]
    list1=list[0::3]
    list2=list[1::3]
    list3=[]
    if len(list1)>len(list2):
        list3.append(list1.pop())
    print("%s|%s"%(list1,list2))
    side=input("(0,1,2) for (neither,left,right) is %s"%heavy)
    if side==2:
        return weigh(list2, heavy)
    if side:
        return weigh(list1, heavy)
    for i in list[2::3]:
        list3.append(i)
    return weigh(list3, heavy)
#End Function, begin rest of program
#This part of the program is long because I need to determine whether the odd ball
#is heavy or light
list=range(input("Number of Balls: "))
#split the list into 3
list1=list[0::3]
list2=list[1::3]
list3=list[2::3]
#make list3 the odd man out, if there is one
if len(list1)>len(list2):
    list1,list3=list3,list1
print("%s|%s"%(list1,list2))
side=input("(0,1,2) for (neither,left,right) is heavier")
#if side==0
if not side:
    heavy="heavier"
    if len(list3)<len(list1):
        list3.append(list2.pop())
    elif len(list3)>len(list1):
        list2.append(list3.pop())
    print("%s|%s"%(list1,list3))
    side2=input("(0,1,2) for (neither,left,right) is heavier")
    if side2==1:
        heavy="lighter"
    print("%s: %s"%(weigh(list3, heavy),heavy))
else:
    if side==2:
        list1,list2=list2,list1
    if len(list3)!=len(list2):
        if len(list3)<len(list1):
            list3.append(list1.pop())
        if len(list3)>len(list2):
            list1.append(list3.pop())
        print("%s|%s"%(list2,list3))
        side2=input("(0,1,2) for (neither,left,right) is heavier")
        if not side2:
            print("%s: heavier"%weigh(list1, "heavier"))
        else:
            possibleAns = list3.pop()
            list3.append(list1.pop())
            print("%s|%s"%(list2,list3))
            side3=input("(0,1,2) for (neither,left,right) is heavier")
            if not side3:
                print("%s: heavier"%possibleAns)
            else:
                print("%s: lighter"%weigh(list2,"lighter"))
    else:
        print("%s|%s"%(list2,list3))
        side2=input("(0,1,2) for (neither,left,right) is heavier")
        if not side2:
            print("%s: heavier"%weigh(list1,"heavier"))
        else:
            print("%s: lighter"%weigh(list2,"lighter"))

```

This program works by dividing the balls into three lists, comparing them to see which of heavier or lighter the ball is, then recursively finds it.
> 0 votes

# Answer
# JavaScript 1281

```
// Weigh function
function weigh(a,b) {
    weigh.count++;
    var len = a.length;
    if (len !== b.length) {
        throw({name:"NotEqual",message:"Can not compare."});
    }
    var wa, wb;
    wa = wb = 0;
    for(var i = 0; i < len; i++) {
        wa += a[i];
        wb += b[i];
    }
    return (wa === wb) ? 0 : (wa > wb) ? -1 : 1;
}
weigh.count = 0;

function findOddBall(arr) {
    var s = [arr];
    var isHeavy = true;
    var priorR = null;
    var left = null;
    var right = null;
    //console.log(arr);
    while(k=s.pop()) {
        //console.log('isHeavy:' + isHeavy + ' ' + k.slice(0));
        var len = k.length;

        if (len === 1) {

            if (priorR !== 0) {
                return [k[0], isHeavy]
            }

            var r = priorR = weigh([left[0]],k);

            if (r !== 0) {
                // we know that the oddball is one of these.. but which one?
                // we need to do a final comparison with the right side.
                priorR = r;
                r = weigh([right[0]],k);

                if (r === 0) {
                    // prior heavy/light
                    isHeavy = (priorR === -1)?true:false;
                    return [left[0],isHeavy]
                } else if(r === 1) {
                    return [k[0], true] // heavy
                }

                return [k[0], false] //light
            }

            continue;
        }

        x = (len % 2 === 0) ? len : len-1;
        right = k.splice(0,x);

        if(k.length !== 0) {
            s.push(k); // remainder
        }

        left = right.splice(0,x/2);
        var r = priorR = weigh(left, right);
        if (r === 0) {
            // We chose a normal side. Test the other side.
            isHeavy = !isHeavy;
        } else if ((r === -1 && isHeavy)|| (r === 1 && !isHeavy)) {
            s.push(right);
            s.push(left); // left is heavier / lighter
        } else if((r === 1 && isHeavy)|| (r === -1 && !isHeavy)) {
            s.push(left);
            s.push(right); // right is heavier / lighter
        }
    }
    throw({name:"NotFound",message:"Can not find oddball."});
}

function main() {

    var total = 0;
    var variations = 0;
    var start = 8;
    var end = 100;

    function test(isHeavy) {
        var normal = (isHeavy) ? 0 : 1;
        var oddball = (isHeavy) ? 1 : 0;
        var score = 0;
        var base = [];

        for (var i=0; i < start;i++) {
            base.push(normal);
        }

        for (var i=start; i <=end; i++) {
            base.push(normal);
            var max = 0;
            for (var j=0; j<i; j++) { // try each placement
                var arr = base.slice(0);
                arr[j]=oddball;
                variations++;
                weigh.count = 0; // reset the scale
                var result = findOddBall(arr);
                if (result[0] !== oddball || result[1] !== isHeavy) {
                    console.log(i);
                    throw({name:"WrongAnswer",message:"Returned wrong answer."});
                }
                if (weigh.count > max) {
                    max = weigh.count;
                }
                //console.log(variations);
            }
            total+=max;
        }
    }

    test(true);
    test(false);

    console.log(variations);
    console.log(total);
}

main();

```
> 0 votes

---
Tags: code-challenge, puzzle-solver
---


title: Broken calculator

text:
# Question
Title: Broken calculator
The functions receives 5 numbers, let's call them a, b, c, d and e
You must display two numbers.
First one is (((a + b) - c) * d) % e = f
Second one is (((a + b) - c) * d - f) / e

```
Input:             Output:
7  5  9  3 8       1 1
1  2  3  4 5       0 0
19 25 9  7 11      3 22
21 12 99 3 13      -3 -15
21 12 99 3 -4      -2 49

```

Requirement: You are not allowed to use '***+***' '***-***' '*******' '***/***' symbols (or equivalent) when doing the calculation. You may however use '***%***' symbol (or equivalent) when doing the calculation.
By equivalent I meant that you are not allowed to use functions such as `BigInteger.add()` (**I am looking at you java users**).

Shortest code wins.

EDIT: as Peter suggested a clarification. All input numbers are int, and will never be 0

# Answer
# Mathematica, 54 chars

I just use dot product.

```
f={Mod@##,Quotient@##}&[{{#,#2,#3}.{1,1,-1}}.{#4},#5]&

```

Example:

```
f[19, 25, 9, 7, 11]

```

> {3, 22}
> 3 votes

# Answer
## Forth, 323 chars

```
: u 2dup ;
: p swap ;
: t -rot ;
: a u xor t and begin ?dup while 2* u xor t and repeat ;
: n invert 1 a ;
: m dup 0 < if p n p n then 0 p 0 ?do over a loop nip ;
: d dup 0 < t p dup 0 < t abs p abs p 0
begin t u <= while over n a rot 1 a repeat 2drop t xor if n then ;
: y 4 roll 4 roll a 3 roll n a rot m p u mod . d . ;

```

The forbidden arithmetic operations are defined in terms of binary operations. The core Forth word `mod` is used as the equivalent of `%`.

The final word `y` is the top-level function that accepts five numbers and prints two numbers as output.
> 5 votes

# Answer
**C++ 503 characters**

```
#include<iostream>
#define I int
#define R return
#define T (I x,I y)
I A T{I a,b;do{a=x&y;b=x^y;x=a<<1;y=b;}while(a);R b;}
I N(I v){R A(~v,1);}
I S T{R A(x,N(y));}
I V(I v){R v<0?N(v):v;}
I M T{I a=0;I i=0;while(i<V(x)){i=A(i,1);a=A(a,y);}R x<0?S(0,a):a;}
I D T{I a=0;x=y==0?0:x;while(M(V(y),a)<V(x))a=A(a,1);R M(y==0?0:S(A(a,1),(x%y==0?1:2)),x<0^y<0?N(1):1);}
void C(I a,I b,I c,I d,I e){I g,f;f=(g=M(S(A(a,b),c),d))%e;std::cout<<f<<' '<<D(S(g,f),e);}
I main(I a){I b,c,d,e;std::cin>>a>>b>>c>>d>>e;C(a,b,c,d,e);}

```

I get the same results as your examples except for the last two, I get -3 -15 and -2 49 respectively. This is the same result that I get from the following...

```
int f = (((a + b) - c) * d) % e;
std::cout << f << ' ' << (((a + b) - c) * d - f) / e;

```
> 3 votes

---
Tags: code-golf
---


# Question
Title: Given a string find the substring which appears most often
Write a complete program (not just a function) which using stdin takes in a string of arbitrary length (assume string-length at least one) composed only of digits 0-9 and outputs using stdout the substring which appears most often in the input string. The input string can be any length and the substring can be maximum half the length of the input string because it must appear at least twice non-overlapped to be printed.

We following the following hierarchy selecting the substring to be printed.

1. First priority, the longest substring
2. Second priority, if we have multiple substrings of the same length, we pick the one appearing the most often.
3. Third priority, if multiple substrings of the same size appear the same number of times, pick the one which appears first scanning from the left.

Here are some test cases followed by the rules and some explanation.

```
./myprogram 123456
No substrings repeat.

```

The substring must appear more than once. If no substrings repeat the the output must exactly be the string "No substrings repeat." complete with the capitalization and the period.

```
./myprogram 12121
12

```

The sub-strings must not overlap. So in this case the largest repeating substring is `12` instead of `121`.

```
./myprogram 99999999
9999

```

We want the largest substring which appears at least twice. Here `9`, `99`, `999`, and `9999` all appears at least twice. But we want the largest substring which appears at least twice.

```
./myprogram 321321788788788
788

```

`321`, `788`, `887`, and `878` each appear multiple times so we pick `788` which appears the most often.

```
./myprogram 12121
12

```

`12` and `21` both appear twice so we pick `12` which appears first from the left.

```
./myprogram 12012112299999999
9999

```

The string `12` occurs first and appears thrice but `9999` is longer and appears only twice so we pick `9999` because it has the highest priority.

```
./myprogram 56698853211564788954126162561664412355899990001212345
412

```

No substrings of length more than three repeat. `412`, `616`, and `123` each appear twice. `412` occurs first and is thus printed.

I think I have taken care of all the cases. True code-golf. The shortest code in any language wins. In the case of ties, I pick the one with the highest upvotes after waiting at least for two weeks and probably longer. So the community please feel free to upvote any solutions you like. The cleverness/beauty of the code matters much more than who posts first.

Happy coding!

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

```
"No substrings repeat."\:i,,{){i@><}+i,,%.{i\/,}%$-1=.2>*{i@/,=}+,0=}/]-1=

```

Brute force GolfScript approach (which would have been much shorter if `$` would be stable). Note that the input must include the newline in order to give correct results.

# Answer
> 3 votes
## Perl, 99 (+1) bytes

```
$_=$;{(sort%;)[m{(.+).*\1(?{$;{$;x$+=~y///c.1x@{[/$+/g]}.2x$+[1]}=$+})^}]}
||"No substrings repeat."

```

*Requires a `-p` command line switch.*

For each repeated substring a hash entry is created, such that the largest substring, repeated the most times, with the earliest position is guaranteed to be the smallest key in the hash. The hash is then sorted, and the corresponding value for the smallest key is output.

Sample Usage:

```
$ echo 123456 | perl -p repeated-substring.pl
No substrings repeat.

$ echo 12121 | perl -p repeated-substring.pl
12

$ echo 99999999 | perl -p repeated-substring.pl
9999

$ echo 321321788788788 | perl -p repeated-substring.pl
788

$ echo 12012112299999999 | perl -p repeated-substring.pl
9999

$ echo 56698853211564788954126162561664412355899990001212345 | perl -p repeated-substring.pl
412

```

# Answer
> 3 votes
# ruby, 104 characters

```
r=gets.size.downto 1
r.find{|l|r.find{|c|$><<$1 if/(.{#{l}})(.*\1){#{c}}/}}||$><<"No substrings repeat."

```

Uses my favourite, nested `find`s. Also, good old magic variables and other perlisms.

# Answer
> 2 votes
## Ruby, 108+1=109

```
$_=$_.scan(/(.+)(?=.*\1)/).map(&:first).max_by{|s|[s.size,$_.scan(s).size,-~/#{s}/]}||'No substrings repeat.'

```

Usage:

```
echo 56698853211564788954126162561664412355899990001212345 | ruby -p repeats_most_often.rb

```

I could save a few chars if I assumed Ruby's sort was stable, but it's not always. Also in older versions of Ruby I could replace the `$_.scan` with `scan`.

# Answer
> 1 votes
# C#, 120 chars

```
Regex.Matches("(.{2,}).*\1",input).Select(n=>n.ToString()).OrderBy(n=>n.Length).LastOrDefault()??"No substrings repeat."

```

## With boilerplate, 171

```
class A{int Main(string[] a){Console.WriteLine(Regex.Matches("(.{2,}).*\1", a[0]).Select(n=>n.ToString()).OrderBy(n=>n.Length).LastOrDefault()??"No substrings repeat.");}}

```

---
Tags: code-golf, string
---


# Question
Title: Code that rot13s the output when it is rot13'd
In case the title was confusing, I mean something like the following C code:

```
main(){}znva(){}

```

When rot13 encoded, the code becomes

```
znva(){}main(){}

```

and still runs.

But that isn't a valid answer, because of these rules:

* Your code must produce output. Code that doesn't produce output is disqualified.
* The program can't be empty. That's disqualified too.
* The program can't be the same or similar to the output. This means that you can't use Golfscript or PHP.

In a valid answer, the program produces some output without being rot13'd, such as:

```
Hello, World!

```

And when the program is rot13'd, the output changes to the following:

```
Uryyb, Jbeyq!

```

which is the rot13 of `Hello, World!`.

Have fun!

# Answer
> 4 votes
## Ruby

Cheaty answer:

```
$><<'Hello, world!'

```

Slightly less cheaty answer:

```
s='Hello, world!'
$-I?puts(s):chgf(s)

```

Golf (15 chars)

```
$-I?p(:a):c(:a)

```

# Answer
> 2 votes
## Perl, ~~25~~ ~~14~~ 12 characters

I believe this adheres to all of the requirements:

```
$_=a;fnl;say

```

Outputs `a`. After `rot13` the program looks like this:

```
$_=n;say;fnl

```

and outputs `n`.

# Answer
> 1 votes
## Brainf\**k

Since you never said the output had to actually be affected by rot13, this is totally a valid answer:

```
-.

```

Not sure why it was downvoted, although it is kind of a cheap answer.

# Answer
> 0 votes
### PHP 6

```
H<?//a

```

The program and its output differ by 83%, so not similar.
`a` is not transformed into output, should satisfy all rules now.

# Answer
> 0 votes
# bash, 64 chars

```
_() { [[ "${1:0:1}" > U ]]&&rpub $@||echo $@; };_ Hello, Jbeyq.

```

---
Tags: code-challenge
---


title: How random is the Gettysburg Address

text:
# Question
Title: How random is the Gettysburg Address
Your program must print out the Gettysburg Address.

I copied this text from Wikipedia:

> Four score and seven years ago our fathers brought forth on this continent a new nation, conceived in liberty, and dedicated to the proposition that all men are created equal. Now we are engaged in a great civil war, testing whether that nation, or any nation so conceived and so dedicated, can long endure. We are met on a great battlefield of that war. We have come to dedicate a portion of that field, as a final resting place for those who here gave their lives that that nation might live. It is altogether fitting and proper that we should do this. But, in a larger sense, we can not dedicate, we can not consecrate, we can not hallow this ground. The brave men, living and dead, who struggled here, have consecrated it, far above our poor power to add or detract. The world will little note, nor long remember what we say here, but it can never forget what they did here. It is for us the living, rather, to be dedicated here to the unfinished work which they who fought here have thus far so nobly advanced. It is rather for us to be here dedicated to the great task remaining before us—that from these honored dead we take increased devotion to that cause for which they gave the last full measure of devotion—that we here highly resolve that these dead shall not have died in vain—that this nation, under God, shall have a new birth of freedom—and that government of the people, by the people, for the people, shall not perish from the earth.

There are two different tests:

1. You may use system decompression software
2. No using system decompression software

Additionally, none of the words in the Address can appear in plain text in your code (with a non-alpha character before and after). Shortest code wins. Good luck!

# Answer
## Tcl, 759, no compression

```
puts [encoding convertt unicode 潆牵猠潣敲愠摮猠癥湥礠慥獲愠潧漠牵映瑡敨獲戠潲杵瑨映牯桴漠桴獩挠湯楴敮瑮愠渠睥渠瑡潩Ɱ挠湯散癩摥椠楬敢瑲ⱹ愠摮搠摥捩瑡摥琠桴牰灯獯瑩潩桴瑡愠汬洠湥愠敲挠敲瑡摥攠畱污潎⁷敷愠敲攠杮条摥椠牧慥⁴楣楶慷Ⱳ琠獥楴杮眠敨桴牥琠慨⁴慮楴湯牯愠祮渠瑡潩潳挠湯散癩摥愠摮猠敤楤慣整Ɽ挠湡氠湯湥畤敲敗愠敲洠瑥漠牧慥⁴慢瑴敬楦汥景琠慨⁴慷⹲圠慨敶挠浯潴搠摥捩瑡潰瑲潩景琠慨⁴楦汥Ɽ愠⁳楦慮敲瑳湩汰捡潦⁲桴獯桷敨敲朠癡桴楥⁲楬敶⁳桴瑡琠慨⁴慮楴湯洠杩瑨氠癩⹥䤠⁴獩愠瑬杯瑥敨⁲楦瑴湩湡牰灯牥琠慨⁴敷猠潨汵潤琠楨⹳䈠瑵湩愠氠牡敧⁲敳獮ⱥ眠慣潮⁴敤楤慣整敷挠湡渠瑯挠湯敳牣瑡ⱥ眠慣潮⁴慨汬睯琠楨⁳牧畯摮桔牢癡敭Ɱ氠癩湩湡敤摡桷瑳畲杧敬敨敲慨敶挠湯敳牣瑡摥椠ⱴ映牡愠潢敶漠牵瀠潯⁲潰敷⁲潴愠摤漠⁲敤牴捡⹴吠敨眠牯摬眠汩楬瑴敬渠瑯ⱥ渠牯氠湯敲敭扭牥眠慨⁴敷猠祡栠牥ⱥ戠瑵椠⁴慣敮敶⁲潦杲瑥眠慨⁴桴祥搠摩栠牥⹥䤠⁴獩映牯甠⁳桴楬楶杮慲桴牥潴戠敤楤慣整敨敲琠桴湵楦楮桳摥眠牯桷捩桴祥眠潨映畯桧⁴敨敲栠癡桴獵映牡猠潮汢⁹摡慶据摥瑉椠⁳慲桴牥映牯甠⁳潴戠敨敲搠摥捩瑡摥琠桴牧慥⁴慴歳爠浥楡楮杮戠晥牯獵琭慨⁴牦浯琠敨敳栠湯牯摥搠慥敷琠歡湩牣慥敳敤潶楴湯琠桴瑡挠畡敳映牯眠楨档琠敨⁹慧敶琠敨氠獡⁴畦汬洠慥畳敲漠敤潶楴湯琭慨⁴敷栠牥楨桧祬爠獥汯敶琠慨⁴桴獥敤摡猠慨汬渠瑯栠癡楤摥椠慶湩琭慨⁴桴獩渠瑡潩Ɱ甠摮牥䜠摯桳污慨敶愠渠睥戠物桴漠牦敥潤⵭湡桴瑡朠癯牥浮湥⁴景琠敨瀠潥汰ⱥ戠⁹桴数灯敬潦⁲桴数灯敬桳污潮⁴数楲桳映潲桴慥瑲⹨]

```
> 6 votes

# Answer
# Mathematica 40

**Note**: Not to be taken as a serious answer. ;)

Just for fun:

```
ExampleData@{"Text","GettysburgAddress"}

```

> Four score and seven years ago, our fathers brought forth upon this continent a new nation: conceived in liberty, and dedicated to the proposition that all men are created equal. Now we are engaged in a great civil war...testing whether that nation, or any nation so conceived and so dedicated. . . can long endure. We are met on a great battlefield of that war. We have come to dedicate a portion of that field as a final resting place for those who here gave their lives that this nation might live. It is altogether fitting and proper that we should do this. But, in a larger sense, we cannot dedicate...we cannot consecrate... we cannot hallow this ground. The brave men, living and dead, who struggled here have consecrated it, far above our poor power to add or detract. The world will little note, nor long remember, what we say here, but it can never forget what they did here. It is for us the living, rather, to be dedicated here to the unfinished work which they who fought here have thus far so nobly advanced. It is rather for us to be here dedicated to the great task remaining before us...that from these honored dead we take increased devotion to that cause for which they gave the last full measure of devotion... that we here highly resolve that these dead shall not have died in vain...that this nation, under God, shall have a new birth of freedom...and that government of the people, by the people, for the people, shall not perish from this earth.
> 18 votes

# Answer
# Python 2.7, no decompression, 962 characters

`"eJxlVEGO2zAM/AofYOQRPbTopacCPdMWbQsri6kk28jvOxTjbNpegliiyJnhkF91L1QnLUKcA1U5JNNDuFTiRcluZ26r4Hssui9ro1lLW0kztTVWmjS3mCU3YspyUuYWNQ92Pkk8JFDMlOIopT2GXiNIiBM33DRFDqF70bvWaO/wzciUEm3AwUA1Femx8nvndKMfetIp/UbywovnZ1osjKZ4xEQnl4GaVOBa6FzF4HviC5wWIHk8P6nqG9qugn6CBBMGAUUqyWEvcqNfXn+TZipctUduLckcJQXS2esBSQ9f+QAT3cQoX6nx8g4pDcEV319DJYiP/5kTlSeNe+JJTHoEahXQUgItocVSg2EsUPmQ6one2NIWrWt2eaPvjdAzTk0Xl2WOrec32taHSyloXFfdwSVob/SNvuxtcLETlwWBVXKVwUJNoqztRe2vQ2hbZSr/Hq/oMprZTbTAWjnc6CfcMBZjhPYPhvnCFoQhjLGurezLktAq4z9c2l414AfAnBkdHhU35uC7qv2cRk6JQzADBGmFp+ZFTy2gekYYL0Xro0FE8ozA3vsim2wwMSA81eHHE8C4Q9TmvDA+xboEdT0SIj8oRAd76W9t3Gv3vlMcqPQhGwzfKG8j0nv8nJM9wxOxrjgG3g8UiNPqFUyY2cezv1jdFShiSsDPWcf0APWDYfRwAfGqLzy9dn//34y6xxvXD5OCgQOijDLb4tjr8LRv0c2i4c9VIZ1430yuxh8C89g01358qM+7+tOJ9+r+fmN1eRuGq8i+97XAFUNoE3PlGF6OdeqwO6hicDT1596FKo6lmu+eBsR1iL5BDlAarmAoc20K2BICfVOYz1/2V77qxtgX4QzeIkE3X289xwLrlbzZWuyzjSUnek/mlsdfnz7Rn9+f8DCK6PVLU8JObuvtD0gQCHY=".decode('base64').decode('zlib')`

**For fun, Python 2.7, no decompression, 1470 characters**

```
"Sbhe fpber naq frira lrnef ntb bhe snguref oebhtug sbegu ba guvf pbagvarag n arj angvba, pbaprvirq va yvoregl, naq qrqvpngrq gb gur cebcbfvgvba gung nyy zra ner perngrq rdhny. Abj jr ner ratntrq va n terng pvivy jne, grfgvat jurgure gung angvba, be nal angvba fb pbaprvirq naq fb qrqvpngrq, pna ybat raqher. Jr ner zrg ba n terng onggyrsvryq bs gung jne. Jr unir pbzr gb qrqvpngr n cbegvba bs gung svryq, nf n svany erfgvat cynpr sbe gubfr jub urer tnir gurve yvirf gung gung angvba zvtug yvir. Vg vf nygbtrgure svggvat naq cebcre gung jr fubhyq qb guvf. Ohg, va n ynetre frafr, jr pna abg qrqvpngr, jr pna abg pbafrpengr, jr pna abg unyybj guvf tebhaq. Gur oenir zra, yvivat naq qrnq, jub fgehttyrq urer, unir pbafrpengrq vg, sne nobir bhe cbbe cbjre gb nqq be qrgenpg. Gur jbeyq jvyy yvggyr abgr, abe ybat erzrzore jung jr fnl urer, ohg vg pna arire sbetrg jung gurl qvq urer. Vg vf sbe hf gur yvivat, engure, gb or qrqvpngrq urer gb gur hasvavfurq jbex juvpu gurl jub sbhtug urer unir guhf sne fb aboyl nqinaprq. Vg vf engure sbe hf gb or urer qrqvpngrq gb gur terng gnfx erznvavat orsber hf—gung sebz gurfr ubaberq qrnq jr gnxr vapernfrq qribgvba gb gung pnhfr sbe juvpu gurl tnir gur ynfg shyy zrnfher bs qribgvba—gung jr urer uvtuyl erfbyir gung gurfr qrnq funyy abg unir qvrq va inva—gung guvf angvba, haqre Tbq, funyy unir n arj ovegu bs serrqbz—naq gung tbireazrag bs gur crbcyr, ol gur crbcyr, sbe gur crbcyr, funyy abg crevfu sebz gur rnegu.".encode('rot13')

```
> 2 votes

# Answer
## Perl, 932 bytes (no system decompression)

This entry is not a UTF-8-encoded file. Perl 5 uses 8-bit characters as its default character set for scripts. Since the website does use UTF-8, I'm posting a base64-encoded version of my submission:

```
c3ViIGJ7JCRfP2IoQCQkXyk6cHJpbnQgZm9yQF99c3ViIGF7JHtjaHIoKX09W3BvcCxwb3BdZm9y
IDE0OS4uMjU1OyZifWEiRpjQY/P71K123iB5Zepz3GfAmOthxHO7ctivvfog9fbBynTy3vlhlneq
98qg16LMaWL8dHn31JvounLCb3O/5tth/yCuIKZj7PHvZXF1/eNOsiDgpt6cZ6LcIJpj12lsIHfq
93S2peFlxNtuzvfa8Hmq0MDKoNfv1HPA0WW3zcz12d5kdezjV/ump/n13CCaYvF0bGVmaWWfx9t3
6uNX+8VjuPvoINH7YSBw87Ugx9tmaWVst8/c6/L9IOxzpXBsYWP7vfZvc/vhwMic6fplaXLM17bb
1W7OIG1pr5dlncH96GdlxOu/pdRwcsL82+BzaNifZG/25+NC/vfy3MzqZ/zQ3nOe0Z7KrWNy8Z68
svbBZ3LYbmTjVGj7Yr7prveXxtSkt+Fv0HRydWdnbO/d5cXKrWNy8e+/92bq3GJv6ZggcG/acLL8
s9xk+NrudL5jdONUaPt38593af/Mv3Rs+25vdOVu2mz12eynbWL8IOH04HNhyd3lYv4gafnNlnb8
6/NnZfnh9PqV3/jdZZ3n69rD4pfyZ/e+xPfou/ubyOjidW5m8udo73fzayDhaWNo9pXhb+vYr8jF
+sPr6tBv0mJsedxkdvCgZJ3BvsTr2sOzu/vIm+jimnTPayDsbWHyxmJlvfvDmWZyuPa2+2j18++k
+OB0YWv78mPsz+/udm+1s9tjYcP7ZtrhaWNo9pWc6fr7bM/5ZnX/IKfPdXL7xyDudm+1meDIaGm5
bMnsc29s6dX6tvuk+KvLxd+iIHZh8pn656r3dW5k/CBHb7erIMVhlne7aXL6IMfr7GVkuC3U1Wdv
dvxurvnHo2J5o72jq8tw/Odo63K44mXq+i5sbHR1bGFyZSBlaHQgdCBkICz6IG5v+WFyb25pdGFu
YfhlZWRuIGVyZiByYft2b3RzafVp92VhaCAu+/Zod/t3aWRuZfxoYSD09iDzIGd1b3ZpY9/0+vjw
8dZv7dPucyBzYebx8GNsIPnS9WMgefvdZm/Z8unk/PpzdXBvIOcgb3RpYXLzZv/kYiBw4mhnbW/3
ZHNl5nTCZeggd2/lbLS6+bnebWVzzeC8c87trOX07GVt++rGdGHusbDy70njZWP4bMup+aFhZ+/R
qGfVLXLY12xl7cllIj1+Ly4vZ3M=

```

This is what the script looks like with the non-ASCII characters replaced with question marks, and some line breaks added for readability:

```
sub b{$$_?b(@$$_):print for@_}sub a{${chr()}=[pop,pop]for 149..255;&b}
a"F??c????v? ye?s?g???a?s?r???? ????t???a?w???????ib?ty?????r?os???a? ? ?c???equ??N? ????
g?? ?c?il w??t???e??n????y????????s??e??????du??W?????? ?b?tlefie???w??W??c??? ??a p?? ??
fiel?????? ?s?plac???os???????eir?????n? mi??e????ge?????pr????sh??do???B??????g???s?????
cr??????gr?nd?Th?b??????????o?truggl??????cr????f??bo?? po?p????d???t?ct?Th?w??wi???tl?no
t?n?l????mb? ???sa???b? i???v???ge????????e????????g???????????unf??h?w?k ?ich???o???????
???o?bly?dv??d???????????????t?k ?ma??be????fr????h??????tak??c????vo???ca??f??ich??????l
??fu? ??ur?? ?vo????hi?l??sol???????????? va??????und? Go?? ?a?w?ir? ???ed?-??gov?n????by
?????p??h?r??e??.lltulare eht t d ,? no?aronitana?eedn erf ra?votsi?i?eah .??hw?widne?ha
?? ? guovic???????o???s sa???cl ???c y??fo??????supo ? otiar?f??b p?hgmo?dse?t?e? wo?l???
??mes???s??????em???ta?????I?ec?l????ag???g?-r??le??e"=~/./gs

```

As @Howard mentioned, this doesn't add much to previous kolmogorov-complexity golf challenges. My encryption scheme, sometimes referred to as "re-pair compression" is one I've used before so I won't go into details again here. In short, it's not a very efficient compression scheme, but it has the advantage of requiring very little code for the decompressor. The compressed string itself occupies 638 characters. (The period near the start of the third-to-last line is where the compressed string ends in the source code quoted above.) The remaining 214 characters of the string is the compression dictionary, leaving 80 characters that make up the Perl script proper.
> 1 votes

---
Tags: code-golf, kolmogorov-complexity
---


title: Optimizing my spell casts!

text:
# Question
Title: Optimizing my spell casts!
I'm a young wizard, and I try very hard to not waste mana during my magical encounters.
I have X spells available at any given time and each one of them have its own mana cost Y.
*X,Y being positive integers strictly lower than 11.*
As a beginner, my mana pool fluctuates a lot (it is always lower than 11), and I need help to cast as few spells as possibles (scrolls are expensive, ya know) while emptying my mana pool. If you can't find any spell combination which matches exactly my mana pool's size, you shall then offer me closest (and cheaper) one.

I came to you and your infinite wisdom to help me become the greatest dark wizard. I shall not be disappointed.

**INPUT style (because style is everything):**
**Y;a b c d e f**
Y is the size of the mana pool. (a,b,c,d,e,f) are the spells. There are 6 spells, first one costs 'a' mana, second spell costs 'b' mana, etc.

**INPUT : 4;1 2 3 3 7 6**
I have 4 manas available, and 6 spells available. Two spells cost 1 mana, 1 spell costs 2 mana, two spells cost 3 mana, etc.

**OUTPUT : (3,1)**

---

**INPUT : 3;1 3 5 2 10
OUTPUT : (3)**

---

**INPUT : 8 ; 4 1 9
OUTPUT : (4,1)**

---

**INPUT : 4;1 2 2 3
OUTPUT : (2,2),(1,3)**
You shall output every combination of spells, but there is no need to distinct spells which are the same cost.

The shortest incantation to whatever machine you desire will be granted a profusion of thanks, and a whip of destiny.

# Answer
> 4 votes
### GolfScript, 55 characters

```
[[]]\{{+}+1$%|}/.@{1$0+{+}*.@>!*100*\,-~}+:s%$0={\s=}+,

```

Try it online.

```
> 4 [1 1 2 3 3 7 6]
[[1 3]]

> 3 [1 3 5 2 10]
[[3]]

> 8 [4 1 9]
[[4 1]]

> 4 [1 2 2 3]
[[2 2] [1 3]]

```

# Answer
> 5 votes
### Ruby, ~~114~~ 113 characters

```
x,y=eval gets
(d=0..10).find{|r|d.find{|c|s=y.sort.combination(c).select{|s|s.reduce(:+)==x-r}.uniq
p s if s[0]}}

```

Input: a two-element array of the wizard mana and the spell list, formatted a one-line JSON.

Output: a 2D array of the spell lists, formatted as a one-line JSON, or `nil` if the wizard can cast no spell.

I especially love `x,y = eval gets`. So dangerous and evil, yet so powerful and simple. Perfect for golfing.

Both `sort` and `uniq` are neccessary. Otherwise, this will produce duplicates for input like `[4, [1, 3, 1]]`. I'm not happy about this.

`find` is a useful method for control flow. Its return value is not as useful here, though. Length-wise, it comes on par with `any?`, which return value is even less useful.

Examples:

```
> [4, [1, 2, 3, 3, 7, 6]]
# [[1, 3]]
> [3, [1, 3, 5, 2, 10]]
# [[3]]
> [8, [4, 1, 9]]
# [[1, 4]]
> [4, [1, 2, 2, 3]]
# [[1, 3], [2, 2]]
> [4, [5, 6, 7]]
# nil

```

# Answer
> 5 votes
## APL (87)

```
↑∪m/⍨t=⌊/t←⊃∘⍴¨m←m/⍨t=⌈/t←+/¨m←{a/⍨⊃i≥+/a←k[⍵]}¨⊃,/g,{z/⍨∧/¨2>/¨z←,⍳⍵/⍴k}¨1↓g←⍳⍴k←1↓i←⎕

```

The input format is an APL list, where the first element is the mana pool and the rest of the elements are the spells. The output has each possible combination of spells on a separate line.

```
⎕:    4, 1 2 3 3 7 6
3 1
⎕:    3, 1 3 5 2 10
3
⎕:    8, 4 1 9
1 4
⎕:    4, 1 2 2 3
2 2
3 1

```

Explanation:

* `k←1↓i←⎕`: read a list from the input, and store it in `i`. Drop the first element (mana) and store the rest in `k`.
* `1↓g←⍳⍴k`: generate a list from `1` to the length of `k`, and store it in `g`. Drop the first element, giving `[2..len k]`.
* `{`...: For each of these, get the indices of each unique combination in `k` of length :
    + `z←,⍳⍵/⍴k`: get a -dimensional matrix of indices of length `k`, flatten it, and store it in `z`.
    + `∧/¨2>/¨`: for each coordinate in each index, see if all coordinates for the `N`th dimension are higher than those for the `N-1`th dimension.
    + `z/⍨`: select from `z` those elements for which the above holds true
* `⊃,/g,`: because the above does not work for one-dimensional vectors, add `g` to the front. We now have a list of lists of lists (because of the foreach) of all unique indices into `k`. Concatenate the lists together and de-enclose (so we end up with a list of lists).
* `{`...: for each possible list of coordinates, look up the corresponding combination of values in `k`, and filter out those that are too expensive:
    + `a←k[⍵]`: look up the current combination in `k` and store it in `a`.
    + `a/⍨⊃i≥+/a`: select `a` only if the first item in `i` (the mana pool) is equal to or greater than the sum of the elements of `a`.
* `m←`: store all combinations of spells that do not exceed the mana limit in `m`.
* `m←m/⍨t=⌈/t←+/¨m`: select from `m` only those combinations whose sum is equal to the sum of the most expensive combination, and store it in `m` again.
* `m/⍨t=⌊/t←⊃∘⍴¨m`: select from `m` only those combinations whose length is equal to the length of the shortest combination.
* `↑∪`: remove any duplicates, and convert to a matrix (to display each combination on a separate line).

# Answer
> 1 votes
### Haskell (GHC), ~~172 167~~ 143 chars

```
import Data.List
import GHC.Exts
f(x:y)=head.groupWith length.last.groupWith sum.filter((<=x).sum).nub$subsequences y
main=interact$show.f.read

```

Deobfuscated:

```
import Data.List
import GHC.Exts

f (x:xs) = head
         . groupWith length
         . last
         . groupWith sum
         . filter ((<= x) . sum)
         . nub
         $ subsequences xs

main = interact (show . f . read)

```
* Input format: bracketed list with head as available mana, tail as avaliable spells (e.g. `[4,1,2,3,3,7,6]`).
* Output format: bracketed list of lists, each sublist representing one possible set of spells.

Straightforward solution: grab the powerset of the input, then reduce that down by filtering for combinations we have sufficient mana for, etc.

# Answer
> 0 votes
# Mathematica 131

There must be shorter ways, but this is what I was able to come up with.

```
l=Length;
f[{a_,b_}]:=Select[t=Cases[s=SortBy[Union@Cases[Subsets[b],x_/;0<Tr@x<a+1:>{x,Tr@x}],Last],
{x_,s[[-1,2]]}:> x],l@#==l@t[[1]]&]

```

---

```
f[{4, {1, 2, 3, 7, 6}}]

```

> {{1, 3}}

---

```
f[{3, {1, 3, 5, 2, 10}}]

```

> {{3}}

---

```
f[{8, {4, 1, 9}}]

```

> {{4, 1}}

---

```
f[{4, {1, 2, 2, 3}}]

```

> {{1, 3}, {2, 2}}

---
Tags: code-golf
---


title: Parse IRC into XML

text:
# Question
Title: Parse IRC into XML
Here's an example IRC log (this will be your program's input):

```
[01:00] == User [*****] has joined #Channel
[01:00] == ChanServ [ChanServ@services.] has left #Channel []
[01:00] == mode/#Channel [+o User] by ChanServ
[01:00] <Bot> Welcome, User!
[01:01] <User> Hello bot
[01:02] <Bot> Hi there
[01:38] <OtherUser> I like pie
[01:38] <User> Me too :D
[19:58] <@Mod> I am a mod!!!1!!11!
[19:59] <User> That's fascinating

```

Your task is to parse that into XML, like this (this will be your program's output):

```
<irc>
  <message type='event'>
    <text>User [*****] has joined #Channel</text>
    <time>01:00</time>
  </message>
  ...
  <message type='chat'>
    <user>Bot</user>
    <text>Welcome, User!</text>
    <time>01:00</time>
  </message>
  ...
</irc>

```

Further specification:

* must be well-formed XML (except for the XML declaration at the top), whitespace/indentation unnecessary
* you don't have to worry about escaping; `>`, `<`, etc. will never appear in messages
* messages can be in two forms:

+ `[{hh:mm}] <{username}> {message}`

    - this should be parsed as:

        ```
        <message type='chat'>
          <user>{username}</user>
          <text>{message}</text>
          <time>{hh:mm}</time>
        </message>

        ```
    + `[{hh:mm}] == {message}`

    - this should be parsed as:

        ```
        <message type='event'>
          <text>{message}</text>
          <time>{hh:mm}</time>
        </message>

        ```
* XML consists of a single `irc` element with zero or more `message` elements in it
* order of the elements within the `message` element don't matter, but order of `message` elements does
* input and output can be any reasonable method (i.e. stdin and stdout, reading from/writing to files, etc.) but input cannot be hardcoded
* this is so shortest code wins

# Answer
### GolfScript, 140 characters

```
{.@+'<>'1/*@+\'</>'2/*+}:^;n%{" "/(1>5<'''time'^\(.'='>{;'event'}{1>-1<'''user'^@+\'chat'}if`' type='\+\' '*'''text'^@+\'message'^}%'''irc'^

```

I meant to use a language, especially designed for xml processing. Input/output is STDIN/STDOUT. You can remove a few chars by replacing `''` with `n` but that makes the output more unreadable.

Output for the example given above (online):

```
<irc><message type="event"><text>User [*****] has joined #Channel</text><time>01:00</time></message><message type="event"><text>ChanServ [ChanServ@services.] has left #Channel []</text><time>01:00</time></message><message type="event"><text>mode/#Channel [+o User] by ChanServ</text><time>01:00</time></message><message type="chat"><text>Welcome, User!</text><user>Bot</user><time>01:00</time></message><message type="chat"><text>Hello bot</text><user>User</user><time>01:01</time></message><message type="chat"><text>Hi there</text><user>Bot</user><time>01:02</time></message><message type="chat"><text>I like pie</text><user>OtherUser</user><time>01:38</time></message><message type="chat"><text>Me too :D</text><user>User</user><time>01:38</time></message><message type="chat"><text>I am a mod!!!1!!11!</text><user>@Mod</user><time>19:58</time></message><message type="chat"><text>That's fascinating</text><user>User</user><time>19:59</time></message></irc>

```
> 4 votes

# Answer
### Tcl, 268

I believe Perl would be better for the job, but who cares.

```
puts <irc>[regsub -all -line {^\[([^\]]*)\] == (.*$)} [regsub -all -line {^\[([^\]]*)\] <([^>]*)> (.*)} [gets stdin] {<message type='chat'><user>\2</user><text>\3</text><time>\1</time></message>}] {<message type='event'><text>\2</text><time>\1</time></message>}]</irc>

```

Every task that can be solved with 2 regsub is boring.
> 1 votes

# Answer
### R 254 characters

```
cat("<irc>",gsub("\\[(.*)\\] <(.*)> (.*)","<message type=\\'chat\\'><user>\\2</user><text>\\3</text><time>\\1</time></message>",gsub("\\[(.*)\\] == (.*)","<message type=\\'event\\'><text>\\2</text><time>\\1</time></message>",scan(,"",se="\n"))),"</irc>")

```

Very simple solution: take input as newline-separated stdin, apply two `gsub` to it (one for events, one for chats) and output.

Example output with example input from question:

```
<irc> <message type='event'><text>User [*****] has joined #Channel</text><time>01:00</time></message <message type='event'><text>ChanServ [ChanServ@services.] has left #Channel []</text><time>01:00</time></message <message type='event'><text>mode/#Channel [+o User] by ChanServ</text><time>01:00</time></message <message type='chat'><user>Bot</user><text>Welcome, User!</text><time>01:00</time></message <message type='chat'><user>User</user><text>Hello bot</text><time>01:01</time></message <message type='chat'><user>Bot</user><text>Hi there</text><time>01:02</time></message <message type='chat'><user>OtherUser</user><text>I like pie</text><time>01:38</time></message <message type='chat'><user>User</user><text>Me too :D</text><time>01:38</time></message <message type='chat'><user>@Mod</user><text>I am a mod!!!1!!11!</text><time>19:58</time></message <message type='chat'><user>User</user><text>That's fascinating</text><time>19:59</time></message </irc>

```
> 1 votes

# Answer
# Ruby: 186 characters

```
BEGIN{puts"<irc>"}
END{puts"</irc>"}
sub(/.(.{5}). (<(.+?)>|==) (.+)/){"<message type='#{$3?:chat:"event"}'>#{$3?"<user>#{$3}</user>":""}<text>#{$4}</text><time>#{$1}</time></message>"}

```

Sample run:

```
bash-4.1$ ruby -p irc2xml.rb < irc.txt
<irc>
<message type='event'><text>User [*****] has joined #Channel</text><time>01:00</time></message>
<message type='event'><text>ChanServ [ChanServ@services.] has left #Channel []</text><time>01:00</time></message>
<message type='event'><text>mode/#Channel [+o User] by ChanServ</text><time>01:00</time></message>
<message type='chat'><user>Bot</user><text>Welcome, User!</text><time>01:00</time></message>
<message type='chat'><user>User</user><text>Hello bot</text><time>01:01</time></message>
<message type='chat'><user>Bot</user><text>Hi there</text><time>01:02</time></message>
<message type='chat'><user>OtherUser</user><text>I like pie</text><time>01:38</time></message>
<message type='chat'><user>User</user><text>Me too :D</text><time>01:38</time></message>
<message type='chat'><user>@Mod</user><text>I am a mod!!!1!!11!</text><time>19:58</time></message>
<message type='chat'><user>User</user><text>That's fascinating</text><time>19:59</time></message>
</irc>

```

Test run:

```
bash-4.1$ ruby -p irc2xml.rb < irc.txt | xmlstarlet val -
- - valid

```
> 1 votes

# Answer
# Sed: ~~183~~ 180 characters

```
1i<irc>
s!.(.{5}). (.*)!\2<time>\1</time>!
Ta
s!<(.+?)> (.*)!chat\n\2<user>\1</user>!
ta
s!== !event\n!
:a
s!(.+)\n([^<]+)!<message type='\1'><text>\2</text>!
a</message>
$a</irc>

```

Sample run:

```
bash-4.1$ sed -rf irc2xml.sed < irc.txt
<irc>
<message type='event'><text>User [*****] has joined #Channel</text><time>01:00</time>
</message>
<message type='event'><text>ChanServ [ChanServ@services.] has left #Channel []</text><time>01:00</time>
</message>
<message type='event'><text>mode/#Channel [+o User] by ChanServ</text><time>01:00</time>
</message>
<message type='chat'><text>Welcome, User!</text><time>01:00</time><user>Bot</user>
</message>
<message type='chat'><text>Hello bot</text><time>01:01</time><user>User</user>
</message>
<message type='chat'><text>Hi there</text><time>01:02</time><user>Bot</user>
</message>
<message type='chat'><text>I like pie</text><time>01:38</time><user>OtherUser</user>
</message>
<message type='chat'><text>Me too :D</text><time>01:38</time><user>User</user>
</message>
<message type='chat'><text>I am a mod!!!1!!11!</text><time>19:58</time><user>@Mod</user>
</message>
<message type='chat'><text>That"s fascinating</text><time>19:59</time><user>User</user>
</message>
</irc>

```

Test run:

```
bash-4.1$ sed -rf irc2xml.sed < irc.txt | xmlstarlet val -
- - valid

```
> 1 votes

# Answer
# Awk: 203 characters

```
BEGIN{print"<irc>"}END{print"</irc>"}{gsub(/\[|\]/,"",$1)
$2=gsub(/<|>/,"",$2)?"<user>"$2"</user>":""
$1="<message type='"($2?"chat":"event")"'><time>"$1"</time>"
$3="<text>"$3
$0=$0"</text></message>"}1

```

Sample run:

```
bash-4.1$ awk -f irc2xml.awk < irc.txt
<irc>
<message type='event'><time>01:00</time>  <text>User [*****] has joined #Channel</text></message>
<message type='event'><time>01:00</time>  <text>ChanServ [ChanServ@services.] has left #Channel []</text></message>
<message type='event'><time>01:00</time>  <text>mode/#Channel [+o User] by ChanServ</text></message>
<message type='chat'><time>01:00</time> <user>Bot</user> <text>Welcome, User!</text></message>
<message type='chat'><time>01:01</time> <user>User</user> <text>Hello bot</text></message>
<message type='chat'><time>01:02</time> <user>Bot</user> <text>Hi there</text></message>
<message type='chat'><time>01:38</time> <user>OtherUser</user> <text>I like pie</text></message>
<message type='chat'><time>01:38</time> <user>User</user> <text>Me too :D</text></message>
<message type='chat'><time>19:58</time> <user>@Mod</user> <text>I am a mod!!!1!!11!</text></message>
<message type='chat'><time>19:59</time> <user>User</user> <text>That"s fascinating</text></message>
</irc>

```

Test run:

```
bash-4.1$ awk -f irc2xml.awk < irc.txt | xmlstarlet val -
- - valid

```
> 0 votes

# Answer
# Perl: 168 characters

```
BEGIN{say"<irc>"}END{say"</irc>"}/.(.{5}). (<(.+?)>|==) (.+)/;say"<message type='",$3?chat:event,"'>",$3&&"<user>$3</user>","<text>$4</text><time>$1</time></message>"

```

Sample run:

```
bash-4.1$ perl -nE 'BEGIN{say"<irc>"}END{say"</irc>"}/.(.{5}). (<(.+?)>|==) (.+)/;say"<message type='"'"'",$3?chat:event,"'"'"'>",$3&&"<user>$3</user>","<text>$4</text><time>$1</time></message>"' < irc.txt
<irc>
<message type='event'><text>User [*****] has joined #Channel</text><time>01:00</time></message>
<message type='event'><text>ChanServ [ChanServ@services.] has left #Channel []</text><time>01:00</time></message>
<message type='event'><text>mode/#Channel [+o User] by ChanServ</text><time>01:00</time></message>
<message type='chat'><user>Bot</user><text>Welcome, User!</text><time>01:00</time></message>
<message type='chat'><user>User</user><text>Hello bot</text><time>01:01</time></message>
<message type='chat'><user>Bot</user><text>Hi there</text><time>01:02</time></message>
<message type='chat'><user>OtherUser</user><text>I like pie</text><time>01:38</time></message>
<message type='chat'><user>User</user><text>Me too :D</text><time>01:38</time></message>
<message type='chat'><user>@Mod</user><text>I am a mod!!!1!!11!</text><time>19:58</time></message>
<message type='chat'><user>User</user><text>That's fascinating</text><time>19:59</time></message>
</irc>

```

Test run:

```
bash-4.1$ perl -nE 'BEGIN{say"<irc>"}END{say"</irc>"}/.(.{5}). (<(.+?)>|==) (.+)/;say"<message type='"'"'",$3?chat:event,"'"'"'>",$3&&"<user>$3</user>","<text>$4</text><time>$1</time></message>"' < irc.txt | xmlstarlet val -
- - valid

```
> 0 votes

---
Tags: code-golf
---


# Question
Title: Decompose a range in aligned blocks of size 2^n
Given an arbitrary contiguous range of positive integers, find the decomposition in the minimum number of sub-ranges of size *L = 2^n*, with the constraint that each range must be aligned, that is the first integer *i* in the sub-range must satisfy *i = 0 (mod L)*.

Background: some (especially old) netblocks aren't a simple single CIDR, that is a range in the form 192.0.2.0/24, but are a composition of several contiguous blocks, and the whois query returns explicitly the first and last ip in the block. Try yourself with `whois 220.72.0.0`:

```
[...]
IPv4 Address       : 220.72.0.0 - 220.91.255.255 (/12+/14)
[...]

```

Solving this problem means finding the list of valid CIDR blocks that summed up constitute this range.

# Answer
> 2 votes
The following greedy algorithm works optimally:

> Choose the larges block allowed which is aligned with the lower bound and does not exceed the total range. Add this range to your result set and remove it from the search space. Loop until the entire range is covered.

In the following lines I took your example and simplified it to the interesting part, i.e. take the range 72-91:

```
0)  Range: 72 - 91 (Size 20)

1a) Largest block size allowed @72: 8
1b) Subrange #1: 72 - 79
1c) Remaining: 80 - 91 (Size 12)

2a) Largest  block size allowed @80: 16 (exceeds size) -> 8
2b) Subrange #2: 80 - 87
2c) Remaining: 88 - 91 (Size 4)

3a) Largest  block size allowed @88: 8 (exceeds size) -> 4
3b) Subrange #3: 88 - 91
3c) Remaining: empty

Result: (72-79) (80-87) (88-91)

```

The structure can be seen even better, if we express the numbers in binary format.

```
0)  Range: 01001000, Size 10100

1a) Largest block size allowed @01001000: 1000
1b) Subrange #1: 01001000, Size 1000
1c) Remaining: 01010000, Size 1100

2a) Largest block size allowed @01010000: 10000 (exceeds size) -> 1000
2b) Subrange #2: 01010000, Size 1000
2c) Remaining: 01011000, Size 100

3a) Largest  block size allowed @01011000: 1000 (exceeds size) -> 100
3b) Subrange #3: 01011000, Size 100
3c) Remaining: empty

```

A note for implementation: the block size for the subrange to be chosen corresponds either to the rightmost 1 bit of the lower bound or the leftmost 1 bit of the size of the range (whichever is smaller).

---
Tags: number-theory, programming-puzzle
---


# Question
Title: Inherit from class with inaccessible abstract members and all constructors inaccessible
The class `System.Globalization.EastAsianLunisolarCalendar` of the `mscorlib.dll` assembly is non-nested `public` but its sole instance constructor is `internal` and it also declares some `internal abstract` members.

**The problem:** Write a C# class in your own assembly (code must compile with usual C# compiler) where a class derives from (inherits) the `System.Globalization.EastAsianLunisolarCalendar` of the BCL.

*Your class must have `System.Globalization.EastAsianLunisolarCalendar` as its* ***direct*** *base class.* It is not allowed to have a third class in "between" your class and that class in the inheritance hierarchy.

(Advanced stuff like dynamic assemblies or runtime IL emission is not needed.)

(Stated as a C# problem. Discussions on whether the equivalent problem can be solved in other object-oriented languages too, will also be considered interesting.)

It is not required that the class you write is usable in any way ;-)

# Answer
Well, I have either to call a base constructor (which is not accessible) or an other constructor in the same class.

```
public abstract class Class1 : System.Globalization.EastAsianLunisolarCalendar {
    private Class1() : this(1) {}
    private Class1(int i) : this() {}
}

```

So let's call the constructors recursive. Not very useful, but who cares?
> 5 votes

# Answer
One way to do it is to inherit a subclass of `System.Globalization.EastAsianLunisolarCalendar`:

```
public class MySubclass : System.Globalization.JapaneseLunisolarCalendar
{
    public static void Test()
    {
        var instance = new MySubclass();

        Console.WriteLine(instance is System.Globalization.EastAsianLunisolarCalendar);
        // this prints "True"
    }
}

```
> 3 votes

---
Tags: programming-puzzle, c#
---


# Question
Title: Test if given number is a Reverse Keith?
Slighty inspired by my previous challenge regarding Keith Numbers I want to propose a challenge to create a function that takes an integer and gives back a true or false depending on the number is a Reverse Keith number or not.

A reverse Keith uses the same little algorithm as Keith numbers, but ends up with it's starting number in reverse.

For example 12 is a Reverse Keith number

> **12**
>
> 1 + 2 = 3
>
> 2 + 3 = 5
>
> 3 + 5 = 8
>
> 5 + 8 = 13
>
> 8 + 13 = **21**

# Answer
> 3 votes
## APL (28)

```
⍙∊{1↓⍵,+/⍵}⍣{⊃⍺≥⍙∘←⍎⌽∆}⍎¨∆←⍞

```

Using more or less the same method as TwiNight did in the other question but reversing the number.

Explanation:

* `∆←⍞`: read a line as text, store in
* `⍎¨`: evaluate each character
* `{1↓⍵,+/⍵}`: add the sum of the list to the end of the list, and drop the first item,
* : until
* `{⊃⍺≥⍙∘←⍎⌽∆}`: the first item on the list is greater or equal to , which is the evaluation () of the reverse () of .
* `⍙∊`: see if  is contained in the final list.

# Answer
> 2 votes
## Perl, ~~126~~ ~~111~~ 110 chars

```
$r=reverse$_=shift;$l=@n=split//;while(1){$t=0;$t+=$_ for@n[-$l..-1];push@n,$t;die"true\n"if$r==$t;last if$t>$r}die"false\n";

```

Should be some room for improvement.

Updated with tips from Dom Hastings:

```
$r=reverse$_=shift;$l=@n=/./g;push(@n,$t=eval join'+',@n[-$l..-1])&&$r==$t&&die"true\n"while$r>$t;die"false\n"

```

You forgot that `$t` isn't being assigned a value with your suggestion, so that adds 3 characters if I want to use that in the following comparisons (it's still cheaper than using `$n[-1]` twice). However, I can save those by changing `split//` to `/./g`.

Slight improvement:

```
$r=reverse$_=shift;$l=@n=/./g;push@n,$t=eval join'+',@n[-$l..-1]and$r==$t&&die"true\n"while$r>$t;die"false\n"

```

Replaced `&&` operators with lower precedence `and` to be able to drop parentheses around call to `push`. Saves one character.

# Answer
> 1 votes
# Mathematica ~~157~~ 96

```
f = (d = IntegerDigits@#; r = FromDigits@Reverse@d;
NestWhile[Rest@Append[#, Tr@#] &, d, Max@# < r &][[-1]] == r) &

```

Based on code by Anton Vrba and considerably streamlined by @ssch.

```
f[11]
f[12]
f[20]
f[24]

```

> False
> True
> False
> True

# Answer
> 1 votes
## PowerShell: 149 135

Mostly derived from my original Keith Number Checker. I'm sure there's still some work to be done.

```
$k=+(($j=($i=+(read-host))-split''|?{$_})[99..0]-join'');While($x-lt$k){$x=0;$j|%{$x+=$_};$null,$j=$j+$x}$x-eq$k-and$i-gt9-and$i%10-ne0

```

I definitely need to double-check for redundant parenthesis and semicolons. It's possible one of the casts to integer is unnecessary. One thing I might also need to spend time on is finding out if I can avoid false-positives without `-and$i%10-ne0`.

It'd be really nice if there was a reliable way to do a left-shift-and-append that's shorter than `$null,$j=$j;$j=@($j);$j+=$x`.

> **EDIT:** Found it! `$null,$j=$j+$x`

Cleanup $x between runs, and also $i, $j, $k when you're done.

# Answer
> 1 votes
## Game Maker Language, 129 136

Make this the function/script `f` and compile with uninitialized variables as 0.

```
a=argument0;while(a>0){b*=10b+=(a mod 10)b div 10}k[]=1k[1]=1while(k[c]<b){c+=1k[c]=k[c-1]+k[c-2]}while(e<c){e+=1if k[e]==b r=1}return r

```

It returns `true` or `false`; call with `f(any number you want)`

**Edit #1** Corrected invalid operators `%` and `/=` with `mod` and `div`.

# Answer
> 0 votes
## Haskell, 106

This version only works for `0 < x < 100` though.

```
k x=(last$takeWhile((>=)x)(let f=(map(Data.Char.digitToInt)$reverse$show x)++zipWith(+)f(tail f)in f))==x

```

**TODO:** check up on Test if given number if a Keith number and implement a proper algorithm.

---
Tags: code-golf, number
---


title: Same code shape and output shape

text:
# Question
Title: Same code shape and output shape
I am not sure if this is possible. I have tried it and couldn't make it work at all, but I am being hopeful.

If this is not possible please flag this question and I will promptly delete it.

Conditions are simple,

Write code that will output same amount of character in the same shape as the code.

For example (A very stupid example).

If code says

```
#include<stdio.h>

main()
{
    printf("Hello World");
}

```

Then output must be

```
kjh#$@#)(12398n,s

lkrjop
t
    jherl;k@&##*$&@3n,2m$*
t

```

I really do not care which characters are being used in the output or anything like that except that space is space and tab is tab. So whatever is the shape of the code, the output should be the same.

**Winner**: Either popularity , or help me decide the criteria.

The only way I managed to make this work, is I created a file reader that reads the code and does rot13 on every character in the code and prints it out. However I was not fond of it, because the shape was not interesting, nor do I want to use file reader to do something like this because it is too easy.

# Answer
> 20 votes
## JS

I know it's still being contested, but I thought I'd have a go:

```
          (function (){a='';
       a           ;         a=
     '             ';           h
    =             '#'            ;
   s             = ' '            ;
  s             ;  s  ;            s
 ;             s   ;   s            ;
s             ;    s    ;            s
;            s     ;     s           ;
s           ;      s      ;          s
;          s       ;       s         ;
 b        =       '';       s       ;
  s      ;      return(      a     +
   b    +     b+arguments[    b   +
    'ca'   +'llee'].toString   ( )
      .replace(/\S/g,h)+'###');s;
          s                 ;
               s;s;s})()

```

When run in Chrome's console produces:

Not 100% accurate, but I thought it was quite close. As intangible as the criteria were to begin with, I did like the idea of the challenge, despite how easy/difficult is in differing languages.

# Answer
> 17 votes
on the Dyalog APL terminal

```
abcde fghij

```

outputs

```
VALUE ERROR

```

# Answer
> 13 votes
## BF

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

```

It just outputs a set of laughing smileys:

```
:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D:D

```

Size of code and its output are both 80.

# Answer
> 7 votes
**Python, 0** (kind of cheating)

Here's a totally *valid* Python program:

And here's the output of that program, of same shape:

:)

# Answer
> 4 votes
## Python

Smallest thing I could think of.

```
print 'a'*5+' '+'a'*16

```

Output

```
aaaaa aaaaaaaaaaaaaaaa

```

That space in the middle is part of a string so it doesn't count.

# Answer
> 3 votes
## Quines

Any quine (a program producing a copy of its own source code) would do the trick. There are thousand examples on the internet written in many different languages. For example:

**Perl, 34** Author: V Vinay

```
$_=q(print"\$_=q($_);eval;");eval;

```

**Python, 33** Author: Frank Stajano

```
l='l=%s;print l%%`l`';print l%`l`

```

**Java, 252** Bertram Felgenhauer

```
class S{public static void main(String[]a){String s="class S{public static void main(String[]a){String s=;char c=34;System.out.println(s.substring(0,52)+c+s+c+s.substring(52));}}";char c=34;System.out.println(s.substring(0,52)+c+s+c+s.substring(52));}}

```

**Tcl, 34** Author: Joe Miller

```
join {{} \{ \}} {join {{} \{ \}} }

```

# Answer
> 1 votes
or if you are picky

```
5 ⍴ 1 + 1

```

outputs

```
2 2 2 2 2

```

# Answer
> 1 votes
## Perl

Any program which reads it's own source file will do (technically, it's not considered to be a quine). Here's a simple Perl script (my lack of inspiration restricted me from giving to the code a shape more complex than a diamond/rhombus)!

```
         use
      warnings;
   use strict;open
(my $IN,'<',$0)or die
   "PCG FTW";print
     <$IN>;close
         $IN

```

Which will print:

```
         use
      warnings;
   use strict;open
(my $IN,'<',$0)or die
   "PCG FTW";print
     <$IN>;close
         $IN

```

# Answer
> 1 votes
# HQ9+

```
 +++    +++
 +++    +++

     ++
++   +Q   ++
++        ++
 ++      ++
  +++  +++
    ++++

```

Or, something like this:

```
                  ___                       __   _____
  ____  ____   __| _/____      ____   ____ |  |_/ ____\
_/ ___\/  _ \ / __ |/ __ \    / ___\ /  _ \|  |\   __\
\  \__(  <_> ) /_/ \  ___/   / /_/  >  <_> )  |_|  |
 \___  >____/\____ |\___  >  \___  / \____/|____/__|
     \/           \/    \/  /_____/                  Q

```

Credits to this site ;)

Basically, anything will work, as long as it has exactly:

* 0 `H`s
* 0 `9`s
* 1 `Q`

Or, some minimalist solutions:

* 1 char

```
Q

```
* 0 chars

# Answer
> 1 votes
### Perl 44 chars

```
open O,"<$0";while(<O>){y|!-~|P-~!-O|;print}

```

In action:

```
echo $'#!/usr/bin/perl\nopen O,"<$0";while(<O>){y|!-~|P-~!-O|;print}' >/tmp/autohide.pl
chmod  +x /tmp/autohide.pl
/tmp/autohide.pl
RP^FDC^3:?^A6C=
@A6? ~[QkS_QjH9:=6Wk~mXLJMP\OM!\OP\~MjAC:?EN

```

reverse:

```
/tmp/autohide.pl | perl -pe 'y|!-~|P-~!-O|'
#!/usr/bin/perl
open O,"<$0";while(<O>){y|!-~|P-~!-O|;print}

```

### Rot47 vs Rot13:

To correspond to *behaviour* of **Rot13**, but from `!` to `~`, there is 94 chars. I wrote `rot47`:

```
#!/usr/bin/perl -s
$                 s
?           $     O
=          *      STDIN
:                   open
$                   O
,                "<"
.                  $
0           ;while
(       <$O>
)      {#
y|!-~|P-~!-O|
;    print   }

```

(I've tried to draw *beavis*, but this is not very well!)

Store them, for sample in `autohide.pl`:

```
chmod  +x autohide.pl

```

with executable rights,

```
./autohide.pl
RP^FDC^3:?^A6C= \D
S                 D
n           S     ~
l          Y      $%sx}
i                   @A6?
S                   ~
[                QkQ
]                  S
_           jH9:=6
W       kS~m
X      LR
JMP\OM!\OP\~M
j    AC:?E   N

```

Than, there is no *reverse* operation, it's only repeat same translation.

When run with `-s` parameter, this use `STDIN` instead of himself code, so running `./autohide.pl -s <autohide.pl` do same as if run without argument:

```
./autohide.pl -s <autohide.pl | ./autohide.pl -s
#!/usr/bin/perl -s
$                 s
?           $     O
=          *      STDIN
:                   open
$                   O
,                "<"
.                  $
0           ;while
(       <$O>
)      {#
y|!-~|P-~!-O|
;    print   }

```

# Answer
> 0 votes
## Python

Generic solution. Just save the file as 'source.py' and execute.

```
import random

def main():
    f = open('source.py')
    s = ''
    d = {' ':1,
     '\t':2,
     '\n' :3}
    rstring = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ`1234567890-=~!@#$%^&*()_+,./<>?;:[]{}|'
    for line in f:
        for char in line:
            if char in d:
                s += char
            else:
                s += random.choice(rstring)
    print s

main()

```

# Answer
> 0 votes
May be simplest solution for Python

```
print'*'*11

```

and for Py3K

```
print('*'*13)

```

and another generic solution for Py3K

import random, sys

```
def main():
    f = open(__file__).read()
    d = ' \t\n'
    r = ''.join(chr(c) for c in range(33, 127))
    sys.stdout.write(''.join(c if c in d else random.choice(r) for c in f))

if __name__ == '__main__':
    main()

```

# Answer
> 0 votes
### Bash ~~9~~ 8 chars (Thanks @FireFly)

```
rot13<$0

```

This match requirement:

* output same amount of character in the same shape as the code
* rot13

### Practical

```
echo  >autorot13.sh 'rot13 <$0'
chmod  +x autorot13.sh
./autorot13.sh
ebg13<$0

```

---
Tags: code-challenge, popularity-contest, code-bowling
---