title: Code Crosswords

text:
# Question
Title: Code Crosswords
*This is a challenge. Answer here if you are a cop (crossword maker), answer the companion question if you are a robber (crossword solver). You may take on both roles.*

# Cops (Puzzlers)

Your task is to write a 10×10 crossword puzzle where, instead of words or phrases, snippets of code are the solutions to clues. Each clue will be a nonempty sequence of characters such that running the snippet of code it refers to will print the sequence to stdout.

Your post must include three things:

1. Your **blank** 10×10 crossword grid, using `#` for *darks* (clue separators) and `_` for *lights* (cells to be filled in).
    * Every horizontal or vertical sequence of 2 or more lights (bounded by darks or the grid edge) is an entry you must write a clue for. For convenience you should number these in the usual way (left-to-right, top-to-bottom) by replacing the `_` at the start of each entry with a unique character identifier (e.g. 1, 2,..., A, B,...).
    * Your grid may have any number of darks.
    * Your grid may have any number of clues.
    * Horizontal entries are always read left-to-right and vertical ones top-to-bottom.
2. A list of clues that contains every entry in your crossword, down and across.
    * Clues must contain at least 1 and no more than 10 characters.
    * If your clues contain spaces make sure they are obvious when you format your post.
3. *Header* and *footer* code snippets, each 20 characters or less.
    * These run respectively before and after a solution snippet, and may help in renaming long built-ins and such.

The procedure for ensuring a clue matches its corresponding code snippet is:

1. Concatenate the header, the snippet, and the footer: `[header][snippet][footer]`.
2. Run this as a normal program (independent of past runs) and look at what was printed to stdout.
3. If this matches the clue the snippet is a valid solution.

For simplicity you may only use printable ASCII (hex codes 20 to 7E) throughout. The header and footer alone may also contain tabs and newlines.

### Additional Notes

* For any snippet, running `[header][snippet][footer]` should not take more than a minute on a decent modern computer.
* You must specify your programming language (and version).
* You may not use any common hashing algorithms.
* You may not use external libraries.
* Everything in your code must be deterministic, time invariant, and not need a network connection.
* `#` and `_` may occur in snippets (or anywhere else).
* You may reveal some of the characters in the crossword as COTO has done. They still count as lights. Robbers are not required to use these, they are just nice hints.

### Example

A simple example using Python 3. Header: `p=print;t=5;`. No footer.

Unsolved grid:

```
##########
1___2___##
_###_#####
_###_#####
_###_#####
####_#####
####_#####
###3______
####_#####
####_#####

```

Clues:

```
ACROSS
1: 8
3: A!
DOWN
1: 7
2: 10

```

Valid solution:

```
##########
print(8)##
(###+#####
7###=#####
)###5#####
####;#####
####p#####
###p('A!')
####t#####
####)#####

```

# Robbers (Solvers)

Your task is to solve the crosswords posted by the cops. You must use the same exact programming language as the crossword was given in, but otherwise any solution that matches all the clues is valid.

You may not solve your own crosswords, and you may only attempt to answer each of the other crosswords once.

Remember to post your solutions in the companion question.

# Scoring

If a crossword is solved within 72 hours it is no longer in the running. Once a crossword has lasted unsolved for 72 hours it is considered immune and the creator may post the solution (by editing their post and marking it immune).

The winning cop is the user who submitted the immune crossword with the fewest darks (`#`). In case of ties the highest voted submission wins. The solution must be posted for the answer to be accepted.

The winning robber is the user who solves the most crosswords. The tie-breaker is their sum of up-votes in the companion question.

# Answer
> 5 votes
# JavaScript, 0 darks – immune

```
 __________
|123456789A|
|B         |
|C         |
|D         |
|E         |
|F         |
|G         |
|H         |
|I         |
|J         |
 ----------

```

Here is the solution for all of you:

```
 __________
|~709-51+90|
|-0x33-31&8|
|8-42^07*70|
|306%4+0x34|
|0xb1204%51|
|-1+2+x>h--|
|'4'*32>>07|
|Math.E>2.7|
|8/2-1-7*22|
|'6'-025036|
 ----------

```

```
Header: var h=8,x=5;console.log(

Footer: );

```

## Clues

```
Across
1. -671
B. 8
C. -460
D. 54
E. 33
F. false
G. 1
H. true
I. -151
J. -10776

Down
1. NaN
2. 15
3. "1131t2"
4. 64
5. -48
6. 49
7. 6
8. true
9. 8
A. 315

```

Let me know if you think there are any results that I miscalculated.

# Answer
> 3 votes
# Python

## Solved by feersum

Here's one to start us off. I used Python 2.7.8 to obtain the clues. Good luck :)

I've revealed the last snippet since hashing is now disallowed. Also, the grid has 36 darks (I missed the scoring part when I made it).

I've revealed a few more characters to make it easier, but different solutions are fine too.

Crossword grid:

```
1_234##5##         * . ## ##
_#6_______         #  e /
_#7__##_##         # * ##6##
8________#        3   %    #
##_#_##_##        ##5# ## ##
#9________        #a   *   b
##_#_##_##        ## # ## ##
A________#        b   7  1 #
##_####_##        ## #### ##
#hash('9')        #hash('9')

```

Clues:

```
ACROSS
1: 440380.9
6: 12328.7671
7: 72
8: 4519217.0
9: 79920L
A: 1.55826556
B: 7296021944

DOWN
1: 1211477643
2: 17353.0
3: 5.4
4: 1719.0
5: 7514613.78

```

Header:

```
a=49481
b=97381
x=

```

Footer:

```
print`x`[:10]

```

# Answer
> 3 votes
# Javascript ES4 - 37 Darks, 10 Reserved

## Solved by bazzarg

### Boards

```
   CLUE #         RESERVED
 __________      __________
|1  2 ###3#|    |     ### #|
| ## #45   |    | ## #I   4|
| ## ## # #|    |:##-## # #|
|6        #|    |         #|
| ## ## # #|    | ## ##.# #|
|7         |    |         ]|
| ## ## ###|    | ## ## ###|
|8   #9    |    | +  #   - |
| ## ## ###|    |'## ## ###|
| ##A      |    | ##   4   |
 ¯¯¯¯¯¯¯¯¯¯      ¯¯¯¯¯¯¯¯¯¯

```

**Header**

```
a=3;I=9;t=

```

**Footer**

```
;console.log(t);

```

### Clues

**Across**

* 1 `51`
* 4 `true`
* 6 `8.14159265` ...
* 7 `"90"`
* 8 `0`
* 9 `-10`
* A `"HI"`

**Down**

* 1 `5`
* 2 `"2pac"`
* 3 `3072`
* 5 `false`

Note that I've included a second representation of the board marked "reserved" to indicate ten lights with characters already filled in. These are to assist the solver and to restrict/disambiguate the possible solutions. I'm not sure whether Calvin wants to count these as darks or lights.

I've used the two separate representations since some of the filled-in characters are numbers and might be confused for clue numbers, and to declutter the board generally.

There are no whitespace characters in any of the solutions, although you're welcome to fill lights with whitespace characters if they work.

**Original Solution**

> `__________
> |{},51###6#|
> |a##+#I/a<4|
> |:##-##[#<#|
> |5+Math.PI#|
> |}##+##.#+#|
> |[I+"0"][0]|
> |'##p##/###|
> |a+-a#a=~-I|
> |'##c##=###|
> |]##"\x48I"|
>  ¯¯¯¯¯¯¯¯¯¯`

As it turns out, bazzarg's solution for 9 across has the `-` in the wrong place, but the clue was supposed to be `10` instead of `-10` (the clue and answer were originally different and I made the switch hastily). Hence we'll just say that two wrongs do make a right in this case. ;)

# Answer
> 3 votes
# C - 26 darks, 5 reserved - solved by feersum

```
   Clue #          Reserved
+----------+     +----------+
|1_2__3_#4_|     |"      #  |
|_#_##_#5_#|     | # ## #  #|
|6___7_8___|     |      8   |
|_#_#9____#|     | # #     #|
|_#AB_#C___|     | #   #    |
|D_#E_____#|     |  #      #|
|_#F#_#_#_#|     | # # # # #|
|_#GH__#I__|     | #    #   |
|_##J_#K#_#|     | ##  # # #|
|L___#M____|     |2 * # _   |
+----------+     +----------+

```

### Header

```
z[4]={9};main(_){_=

```

### Footer

```
;printf("%d",_);}

```

### Clues

```
ACROSS:
1. 48
4. -8
5. -2
6. 0
9. 73
A. 9
C. 0
D. 5
E. 0
G. -2
I. 0
J. 0
L. 18
M. 6247483

DOWN:
1. 45
2. 7680
3. 22
4. -97
5. 0
7. -1073741824
8. 8
B. 0
F. 42
H. 0
K. -2

```

# Answer
> 3 votes
# CJam, 41 darks - solved by Martin Büttner

No header, footer or reserved squares. Let me know of any potential bugs.

The solution I originally had in mind had no whitespace - it is not the one that Martin Büttner found.

## Board

```
#5###6#7__
#4_3____##
1##_#_#_#A
2____##_#_
_##_##9___
_##_#E#_#_
_#C#8_____
##_#_####_
##B_______
D__#_####_

```

## Clues

**Across**

```
2: [[4 3]]
4: 24717
7: 32
8: E
9: "" (there is ONE trailing space after the quotes)
B: "m
D: 124

```

**Down**

```
1: [2 2 2 3]
3: 3010936384
5: 2017
6: "18"
7: ' "\"\""
8: !{}
A: -3u3
C: -1
E: Stack: ""

```

Good luck!

# Answer
> 3 votes
# MATLAB - 28 Darks

## Solved by feersum

### Boards

```
  CLUE #         RESERVED
 __________      __________
|12 3 4 5  |    |    [     |
|# # # # ##|    |#s# # # ##|
|6   # #7 8|    |    # #   |
|# # # # # |    |# # # # # |
|9 A       |    |6  7  y   |
|#B  # # # |    |#   # # # |
|C         |    |        g |
|# # ### # |    |# # ### # |
|# # ##D # |    |# # ##  # |
|E         |    |d         |
 ¯¯¯¯¯¯¯¯¯¯      ¯¯¯¯¯¯¯¯¯¯

```

**Header**

```
g=4;o=magic(3);disp(

```

**Footer**

```
);

```

### Clues

**Across**

* 1 `2`
* 6 `-1i`
* 7 `eye(3)`
* 9 `0`
* B `sqrt(-1)`
* C `1/25000`
* D `0`
* E `[0;0;0]`

**Down**

* 2 `log(1i)`
* 3 `100`
* 4 `10^16`
* 5 `[2,2;2,2]`
* 8 `512`
* A `inv(1i)`
* D `zeros(3)`

Note that I've changed things up slightly in the clues for this puzzle. Since MATLAB outputs are invariably verbose (for example, even printing the imaginary unit `1i` exceeds 10 characters \[`0 + 1.0000i`\]) and change depending on the default output format, the clues are all simple expressions whose *displayed output is equivalent to that of the corresponding solutions*.

In other words, you can consider an actual clue to be `disp( CLUE )`, where `CLUE` is the 10-character-or-less clue in the above lists.

Hopefully Calvin doesn't mind. I don't believe this violates the spirit of the clue length rule, which is likely to prevent crossword builders from inserting extremely-hard-to-generate solutions (i.e. words).

### Key

```
    KEY
 __________
|max([1 2])|
|#s#1#0#*##|
|1i^3#*#o\o|
|#n#+#1#n#(|
|6 -7+eye&1|
|#(i)#1#s# |
|.1 ^ 5*(g)|
|#)#2### #^|
|#*#/##~2# |
|diag(-o)>3|
 ¯¯¯¯¯¯¯¯¯¯

```

# Answer
> 1 votes
## Python 2, 0 darks - Immune

Python 2 is only because of the `print` in the footer. It should work the same way in Python 3 if you change the `print` statement.

I had fun making this, and overall I'm satisfied and a bit excited about the final result.

Let me know if you think my footer is too cruel (if I knew you could refrain from using a program to brute force it, I'd remove the cruelty.) Fun fact: the variables in the header spell 'bread'.

```
 __________
|123456789A|
|B         |
|C         |
|D         |
|E         |
|F         |
|G         |
|H         |
|I         |
|J         |
 ----------

```

**Header:**

```
b=7;r=3;e=6;a=.1;d=

```

**Footer:**

```
;print 2*str(d)[::3]

```

---

## Clues:

**Across**

```
1. 74
B. 282.e2
C. 77
D. 8
E. 94
F. 247351.862e1
G. 99
H. -5312-5312
I. -32
J. 300000

```

**Down**

```
1. 61000
2. 251
3. 09333.8333
4. 7878
5. -70
6. -0045.164
7. 88
8. 61225
9. -350
A. 69971

```

---

**Solution**

> `__________
>  |r+111-37-r|
>  |'2.48e+22'|
>  |6+765-0*56|
>  |30/7%140*2|
>  |0xe6b/0x27|
>  |18**+9.1-9|
>  |047--01551|
>  |04/-7.0131|
>  |0-1512%989|
>  |'30000700'|
>  ----------`

---
Tags: printable-ascii, source-layout, cops-and-robbers, crossword
---


# Question
Title: Find a numeric coincidence when representing numbers in various bases
Recently, when doing some code-golf challenge, I came up with with two solutions, in 69 and 105 bytes. It's a remarkable coincidence, because:

* 69 (decimal) = 105 (octal)
* 69 (hexadecimal) = 105 (decimal)

What other numbers have this property (using different bases)? You should help me answer this question!

Write a program or a subroutine that receives as input 3 numbers (base1, base2, base3, in ascending order), and prints two sequences of digits `d1 d2 d3 ...` and `D1 D2 D3 ...` that reproduce this numerical coincidence for the specified bases.

To make sure the various fine points are covered:

* Evaluate one sequence as a number in base `base1`, and the other sequence in base `base2` -- you must get the same number
* Evaluate one sequence as a number in base `base2`, and the other sequence in base `base3` -- you must get the same number
* Both sequences must have finite length, which is greater than 1
* Separate the sequences of digits with whitespace or in any other unambiguous way
* Output to `stdout` or other similar output device
* All digits must be between 0 and `base-1`; leading zeros are not allowed
* If a digit is greater than 9, use `a` or `A` for 10, `b` for 11, ..., `z` for 35
* You may assume that all bases are different, come in ascending order and are in the range 2...36; are represented in the most natural way for your language
* If there is no answer, your code must signal it in some way (e.g. outputting nothing)
* If there is an answer whose larger number is less than 1679616 (364), your code must find it; otherwise, it may output as if no solution exists
* Code-golf: shortest code wins!

Example input:

```
8, 10, 16

```

Example output:

```
69 105

```

or

```
104 68

```

Or any other solution.

I'll be happy if you provide theoretical insights into this problem (How to determine whether a solution exists? Is there an infinite number of solutions?).

# Answer
## Python 2, 158 bytes

Came a bit too easily, so I might be missing something obvious!

```
s=lambda n,b:(n/b and s(n/b,b)or'')+chr(48+n%b+39*(n%b>9))
def f(a,b,c):
 for n in range(b,36**4):
  x=s(n,a);y=s(n,b)
  if int(x,b)==int(y,c):print x,y;break

```

The base conversion function is lovingly stolen from @ugoren's solution to Print integers in any base up to 36. The code simply tries all possible values for the smaller number and the rest is fully determined. We start counting from *base2* to ensure both sequences are at least length 2.

```
>>> f(8, 10, 16)
100 64
>>> f(8, 10, 17)
>>> f(16, 20, 24)
20 1c

```
> 3 votes

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


# Question
Title: Reading Code in 8 Ways to Output 8 Numbers
The English language and most programming languages are written and read from left-to-right, top-to-bottom, but that needn't be the case.

In fact for the block of text

```
ABC
DEF

```

I can think of eight related ways it might be read:

1. Left-to-right, top-to-bottom (LTR-TTB): `ABCDEF`
2. Top-to-bottom, left-to-right (TTB-LTR): `ADBECF`
3. Left-to-right, bottom-to-top (LTR-BTT): `DEFABC`
4. Bottom-to-top, left-to-right (BTT-LTR): `DAEBFC`
5. Right-to-left, top-to-bottom (RTL-TTB): `CBAFED`
6. Top-to-bottom, right-to-left (TTB-RTL): `CFBEAD`
7. Right-to-left, bottom-to-top (RTL-BTT): `FEDCBA`
8. Bottom-to-top, right-to-left (BTT-RTL): `FCEBDA`

# Challenge

Write a rectangular block of text that can be read in each of the eight ways above as eight **single line** programs in your language of choice. Each of these programs should output a different integer from one to eight.

It doesn't matter which reading direction outputs which number, they do not have to match the numbers above. For example, if your text block were still

```
ABC
DEF

```

then the program `ABCDEF` might output `5` and `FEDCBA` might output `2`, and the other six programs would output `1`, `3`, `4`, `6`, `7`, and `8` in some order.

**The text block may contain any characters except line terminators.**

Output should go to stdout or a similar alternative if your language doesn't have a proper stdout. There is no input. You may assume the programs are run in a REPL environment.

Pietu1998 charitably wrote a JSFiddle that gives the 8 different single line programs when given a block of text. I've made it into a stack snippet:

```
<script>function f(n){n=n.split("\n");var e=n.map(function(n){return n.length}).sort()[n.length-1];n=n.map(function(n){return(n+Array(e+1).join(" ")).substring(0,e)});var t=n[0].split("").map(function(e,t){return n.map(function(n){return n[t]}).join("")});n=[n.join(""),n.reverse().join(""),t.join(""),t.reverse().join("")],n=n.concat(n.map(function(n){return n.split("").reverse().join("")})),document.getElementById("a").innerHTML=n.map(function(n,e){return document.getElementById("b").checked?n+"   "+"LLTTRRBB"[e]+"T"+"RRBBLLTT"[e]+"-"+"TBLRBTRL"[e]+"T"+"BTRLTBLR"[e]:n}).join("\n")}</script><textarea onkeyup="f(this.value)" id="c" placeholder="Code"></textarea><br/><input type="checkbox" id="b" onchange="f(document.getElementById('c').value)" checked/> <label for="b">Show directions</label><br/><pre id="a"></pre>
```

You can still find Martin's CJam version here.

# Scoring

Your score is the area of your block of text (the width times the height). The submission with the lowest score wins. (Essentially the smallest code wins, hence the tag.) Tiebreaker goes to the earlier posted submission.

The example is 2 by 3 so its score is 6. A score less than 4 (2 by 2) is impossible because then some of the 8 programs would be identical and couldn't output two different values.

# Answer
> 21 votes
# J, 3 * 3 = 9

```
1[2
+2+
2+2

```

Executing all directions:

```
       ". '1[2+2+2+2','2+2+2+1[2','1+2[2+2+2','2+2[2+1+2','2+2+2+2[1','2[1+2+2+2','2+2+2[2+1',:'2+1+2[2+2'
1 7 3 4 8 2 6 5

```

Explanation:

* In J execution goes from right to left and there is no operator precedence.
* The `[` (`left`) takes the left side of its two operand so it essentially cancels the whole right side of our expression e.g. `1+2[2+2+2` becomes `1+2[6` and then `1+2`.
* The left expressions are additions with a total of 1, 2, 3 and 4 operands. There are two of each `n`-operand expressions one with the number `1` and one with only `2`s. The additions with `1` generate the odd numbers and the others generate the even ones.

# Answer
> 19 votes
# Befunge-98, ~~5x5 = 25~~ 5x3 = 15

```
1+4+2
$.@.$
3+4+4

```

I wrote a little script that found the correct numbers for me. It took a while, but hey, I just beat GolfScript! :D

The scripts I used are here and here, but I don't suggest looking at them since the code style is extremely carcinogenic.

## Subprograms

```
1+4+2$.@.$3+4+4   LTR-TTB   5
3+4+4$.@.$1+4+2   LTR-BTT   7
1$3+.+4@4+.+2$4   TTB-LTR   3
2$4+.+4@4+.+1$3   TTB-RTL   4
4+4+3$.@.$2+4+1   RTL-BTT   8
2+4+1$.@.$4+4+3   RTL-TTB   6
4$2+.+4@4+.+3$1   BTT-RTL   2
3$1+.+4@4+.+4$2   BTT-LTR   1

```

## Old version

```
 1.6
3 @ 4
.@ @.
8 @ 7
 2.5

```

### Subprograms

Output the numbers 1-8 respectively.

```
 1.6 3 @ 4.@ @.8 @ 7 2.5    LTR-TTB
 2.5 8 @ 7.@ @.3 @ 4 1.6    LTR-BTT
 3.8 1 @ 2.@ @.6 @ 5 4.7    TTB-LTR
 4.7 6 @ 5.@ @.1 @ 2 3.8    TTB-RTL
 5.2 7 @ 8.@ @.4 @ 3 6.1    RTL-BTT
 6.1 4 @ 3.@ @.7 @ 8 5.2    RTL-TTB
 7.4 5 @ 6.@ @.2 @ 1 8.3    BTT-RTL
 8.3 2 @ 1.@ @.5 @ 6 7.4    BTT-LTR

```

# Answer
> 14 votes
# Brainfuck$, 4x3 = 12

Brainfuck$ is very similar to Brainfuck, but has some more commands, including a command to output the current cell value as numeric output, which was very useful for this challenge.

```
++:+
  ++
++++

```

One-line commands:

```
++:+  ++++++   LTR-TTB, outputs 2
++++  ++++:+   LTR-BTT, outputs 8
+ ++ +:+++++   TTB-LTR, outputs 4
+++:+++ ++ +   TTB-RTL, outputs 3
++++++  +:++   RTL-BTT, outputs 7
+:++++  ++++   RTL-TTB, outputs 1
+++++:+ ++ +   BTT-RTL, outputs 5
+ ++ +++:+++   BTT-LTR, outputs 6

```

# Answer
> 7 votes
# TECO, 3\*5 = 15

```
 +4 5
+2=4
 +1 \

```

`=` prints the value of the last numerical expression. `\` is used to read or write numbers from strings, but I use it only as a discard here.

* `+4 5+2=4 +1 \` 7
* `+ +2+4=1 4 5 \` 6
* `+ +2+1=4 4 \ 5` 3
* `+1 \+2=4 +4 5` 2
* `\ 1+ 4=2+5 4+`  5
* `\ 5 4 1=4+2+ +`  1
* `5 \ 4 4=1+2+ +`  4
* `5 4+ 4=2+\ 1+`  8

# Answer
> 7 votes
# piet - 12x12 = 144

Since a one line program can never terminate, assume it terminates after first output.

8 subprograms in a single image:

# Answer
> 6 votes
# GolfScript, 4x4 = 16

```
1})7
)  }
}  )
3)}5

```

Makes use of the good old "super comment": an unmatched `}` ignores the rest of the code (in fact, in this case a normal comment `#` would have worked just as well, since all the code is run as a single line). So from each corner there's either only a single number, or (in the other direction) that number incremented by 1, because execution terminates and the stack contents are printed. The 8 programs are

```
1})7)  }}  )3)}5  # LTR-TTB
1)}3}  ))  }7})5  # TTB-LTR
3})1)  }}  )5)}7  # BTT-LTR
3)}5}  ))  }1})7  # LTR-BTT
5})3)  }}  )7)}1  # RTL-BTT
5)}7}  ))  }3})1  # BTT-RTL
7})5)  }}  )1)}3  # TTB-RTL
7)}1}  ))  }5})3  # RTL-BTT

```

# Answer
> 5 votes
# Haskell, 26x26 = 676

Uses comments (`--`) to hide the backwards and sideways bits. This makes it terribly long

```
main=print 1--2 tnirp=niam
a                        a
i                        i
n                        n
=                        =
p                        p
r                        r
i                        i
n                        n
t                        t

3                        4
-                        -
-                        -
5                        6

t                        t
n                        n
i                        i
r                        r
p                        p
=                        =
n                        n
i                        i
a                        a
main=print 7--8 tnirp=niam

```

# Answer
> 4 votes
# Prelude, 5x3 = 15

```
12 34
  !
56 78

```

This assumes the Python interpreter, which prints values as numbers instead of character codes.

This doesn't beat Befunge$, but it does beat my GolfScript submission, and I like its simplicity. Note also that it uses only 9 non-space characters, ~~which is less than any other submission so far~~ (J strikes again :)). In Prelude, each digit is pushed onto the stack individually, and depending on the path, there's a different digit right before the `!`, which just prints the top stack element. The 8 programs are:

```
12 34  !  56 78   LTR-TTB   4
56 78  !  12 34   LTR-BTT   8
1 52 6 ! 3 74 8   TTB-LTR   6
4 83 7 ! 2 61 5   TTB-RTL   7
87 65  !  43 21   RTL-BTT   5
43 21  !  87 65   RTL-TTB   1
8 47 3 ! 6 25 1   BTT-RTL   3
5 16 2 ! 7 38 4   BTT-LTR   2

```

Alternatively, there's also

```
 1 3
1+!+1
 5 7

```

Which pushes the odd numbers on the vertical paths, and increments them by `1` on the horizontal paths:

```
 1 3 1+!+1 5 7    LTR-TTB   4
 5 7 1+!+1 1 3    LTR-BTT   8
 1 1+5 ! 3+7 1    TTB-LTR   5
 1 3+7 ! 1+5 1    TTB-RTL   7
 7 5 1+!+1 3 1    RTL-BTT   6
 3 1 1+!+1 7 5    RTL-TTB   2
 1 7+3 ! 5+1 1    BTT-RTL   3
 1 5+1 ! 7+3 1    BTT-LTR   1

```

# Answer
> 2 votes
# CJam - 7×7

Not impressive, but there was no CJam answer and I like the way it looks :)

```
 8;];1
7     2
;  0  ;
] 0 0 ]
;  0  ;
6     3
 5;];4

```

It mainly uses the fact that `];` clears the stack.

Try it online

# Answer
> 2 votes
# R, 9x9

No white space, no comments.

```
75%%99299
99%%99699
%%299%%41
%%699%%06
995999997
11%%999%%
99%%799%%
39719%%99
59519%%16

```

I guess this could be expanded to whatever size you want. I thought the modulo operator was most the most flexible of available operators, since it prevents values from being too large regardless of data size, and there's no effect from having really large numbers in between.

```
75%%9929999%%99699%%299%%41%%699%%0699599999711%%999%%99%%799%%39719%%9959519%%16   LTR-TTB  2
59519%%1639719%%9999%%799%%11%%999%%995999997%%699%%06%%299%%4199%%9969975%%99299   LTR-BTT  3
79%%9193559%%91999%%265%%75%%999%%1199999979999%%999%%26%%999%%99409%%9199167%%96   TTB-LTR  4
99167%%9699409%%9126%%999%%99%%999%%999999799%%999%%11%%265%%7559%%9199979%%91935   TTB-RTL  1
61%%9159599%%91793%%997%%99%%999%%1179999959960%%996%%14%%992%%99699%%9999299%%57   RTL-BTT  5
99299%%5799699%%9914%%992%%60%%996%%799999599%%999%%11%%997%%9999%%9179361%%91595   RTL-TTB  6
69%%7619919%%90499%%999%%62%%999%%9999799999911%%999%%57%%562%%99919%%9553919%%97   BTT-RTL  7
53919%%9799919%%9557%%562%%11%%999%%997999999%%999%%99%%999%%6219%%9049969%%76199   BTT-LTR  8

```

# Answer
> 1 votes
# Ruby - 7x7

Not impressive either, same tactic as the Haskell answer.

```
p 1#2 p

3     7
#     #
4     8

p 5#6 p

```

# Answer
> 1 votes
# This Programming Language, 5 * 9 = 45

```
1i;i2
2   2
+   +
i   i
;   ;
i   i
+   +
2   2
5i;i6

```

Which translates into this:

```
1i;i22   2+   +i   i;   ;i   i+   +2   25i;i6
5i;i62   2+   +i   i;   ;i   i+   +2   21i;i2
12+i;i+25i       i;       ;i       i22+i;i+26
22+i;i+26i       i;       ;i       i12+i;i+25
6i;i52   2+   +i   i;   ;i   i+   +2   22i;i1
2i;i12   2+   +i   i;   ;i   i+   +2   26i;i5
62+i;i+22i       i;       ;i       i52+i;i+21
52+i;i+21i       i;       ;i       i62+i;i+22

```

Since `;` terminates the program, the above translates into this:

```
1i;   - outputs 1
5i;   - outputs 5
12+i; - outputs 3
22+i; - outputs 4
6i;   - outputs 6
2i;   - outputs 2
62+i; - outputs 8
52+i; - outputs 7

```

**Explanation:** any number from `0` to `9` pushes the corresponding digit onto the stack. `+` pops the top two values `x` and `y` off the stack and pushes `x + y` onto the stack. `i` outputs the stack as an integer.

---
Tags: code-golf, printable-ascii, source-layout
---


title: Pseudo-cyclic Number Evaluator

text:
# Question
Title: Pseudo-cyclic Number Evaluator
For the purposes of this challenge, let's define a cyclic number as an integer that passes the basic part of Midy's Theorem, but not necessarily the extended theorem. This means:

> the digits in the second half of the ~~repeating decimal period are~~ \[integer is\] the 9s complement of the corresponding digits in its first half

In other words, `142857` is a cyclic number because `142 + 857 = 999` and `13358664` is a cylic number because `1335 + 8664 = 9999`.

## The Challenge

Given an even-digit integer n \> 10, determine whether n is a cyclic number by our definition. If it is, return something truthy. If it's not, return the closest cyclic number to n.

Example:

```
> 18
True
> 133249
132867

```

This is code golf, so shortest code wins.

# Answer
> 1 votes
# Python 2, 73

```
n=input()
e=10**(len(`n`)/2)-1
N=n/e+n%e*2/e;N-=N>e+1
print n==N*e or N*e

```

A six-digit pseudo-cyclic number like `637362` is pseudo-cyclic exactly if it's a multiple of `999`, except for `999999`. So, we're looking for the multiple of `999` nearest to the input `n`. In general, replace `999` with `e`, which is one less that `10**(num_digits/2)`.

The nearest multiple below can `n` be found with integer division as `n/e*e`. We check whether to round up with `n%e*2/e`, which is `1` if `n%e` is closer to `e`, and `0` if it's closer to `0`. In the latter case, we add `e`. We also handle the `999999` case by subtract if `N` is too large.

Finally, before printing, we check if the original number was a multiple of `e` and thus already pseudo-cyclic.

# Answer
> 1 votes
# Pyth, 39

```
Jf!-`sjT^10/l`T2\9UyQ|}QJho%l`N2o^-QZ2J

```

... or

**A version that might be against the rules: 33**

```
ho%l`N2o^-QZ2f!-`sjT^10/l`T2\9UyQ

```

Try it online here.

The rules-breaking version just echoes the number if it is cyclic.

I believe this gives the correct output for all values, if you find something in my reasoning that is flawed, please tell me ;)

This begins by generating a list of all of the cyclic numbers from 0 to twice the input. This will obviously include each cyclic number less than the input, and includes the next cyclic number. You actually only need to add `10 ^ (digits_in_input / 2)` to ensure this, but doubling takes fewer characters.

The numbers are found to be cyclic by converting them into base `10 ^ (digits_in_input / 2)` and then summing the digits of this number together. All `9`s are then removed from this list, and so if the list is empty the number is cyclic.

If the input is a member of this list, `True` is printed, otherwise the list is sorted, first by `(input - value) ^ 2` and then by if the number contains an even or odd number of digits (sorting evens as less). Since pyth uses stable sorts, this is equivalent to sorting by both at once. Then the first number in this list is the nearest cyclic tag number.

This algorithm is fairly naive, but I believe it catches everything. I particularly think that the sorting could be golfed a lot.

# Answer
> 1 votes
# Clip, 59

```
[vr[p[q?<a-vpa-vqp]q]}}f[d[q=qc$+n#q$dn+q$d'9]/l$d2},T*v2]n

```

Straightforward approach. It makes a list of all numbers, where if you the the two halves the result is all 9's, and finds which one is closest to the input. If the input is a cyclic number, it will be printed, which is allowed because all non-zero numbers are truthy.

## Explanation:

```
[v               .- A function of v (which will be set to the input) -.
  r              .- Reduce, to find the best answer                  -.
   [p[q          .- A function of p, q                               -.
       ?         .- If                                               -.
        <        .- Compare                                          -.
         a-vp    .- the distance between one number and the input    -.
         a-vq    .- the distance between another number and the input-.
       p]q]      .- Return the closest                               -.
   }}
  f              .- Filter, to find solutions                        -.
   [d            .- A function of d (each possible value)            -.
     [q          .- Set q as... (half of length of d)                -.
       =q        .- Only if q equals...                              -.
         c       .-  the count, within...                            -.
          $      .-   the string form of...                          -.
           +     .-    the sum of...                                 -.
            n#q$d.-     the first q digits of d                      -.
            n+q$d.-     the last q digits of d                       -.
          '9     .- the digit 9                                      -.
     [/l$d2      .- half of length of d                              -.
   }
  ,T*v2          .- the numbers from 10 to double v                  -.
]n               .- With v set as the numeric value of...            -.

.-implicit-.     .- the first line of input                          -.

```

This passes the test-cases, though I'm not certain that the range is wide enough. If not, it can be increased by changing the `*v2` to `*v9` or greater.

Unfortunately, there's a bug in the interpreter's `s` sort-by function, so I had to use waste a few bytes using the `r` reduce function instead.

# Answer
> 1 votes
# Python 2, 94 characters

```
def r(n):
 i=0;s=1
 while 1:
    n+=i*s;M=10**(len(str(n))/2);i+=1;s=-s
    if n/M+n%M==M-1:return n

```

Note: the last two lines use a tab character for indentation.

Given `n`, this checks numbers for cyclicity in the following order: `n`, `n-1`, `n+1`, `n-2`, `n+2`, etc... If `n` is a cyclic number, it returns `n` (which is a truthy value). If it isn't, it returns the closest one that is.

# Answer
> 1 votes
**Ruby, 79 chars**

```
p->n{t=n.to_s;s=t.size/2;u=t[0...s];v=t[s..-1];u.to_i+v.to_i==('9'*s).to_i}.(13358664)

```

# Answer
> 0 votes
# Bash + coreutils, 118

```
m=$[10**(${#1}/2-1)]
jot -w%dd$1-n32Ppc $[m*9] $m$[m*9-1] $[(m*10-1)*m*10]|dc|tr -d -|sort -n|sed -n "/$1/!s/.* //p;q"

```

Calculates all cyclic numbers with the same number of digits as the input number, then uses `sort` to find the closest. In true unix fashion, nothing is printed for the "true" / "success" case, but the nearest cyclic number is printed if the input is not cyclic.

# Answer
> 0 votes
## Python 3

209 hardcoded or 200 with user input

```
x = [142857, 13358664, 18, 133249]
i=int
def g(x):
    a,b=str(x),i(len(str(x))/2)
    return (lambda d,c:i(d)+i(c)==10**len(d)-1 and x or g(i(d+c)-1))(a[:b],a[b:])
for y in x:print((g(y)==y and True or g(y)))

```

Output:

```
True
True
True
132867

```

The implementation here is fairly simple. I see other entries are quite shorter; so I'm not aiming to win here, just wanted to try. This code-golfing is still very new to me.

**Amendment**

Having user input is simple; with one exception. For some numbers the function will throw a `RuntimeError` if the recursion depth hits its limit while trying to obtain a valid number counting down. That means any reasonable programmer should eat this error apporpriately and simply return `False`. The exception also catches any number below 27.

```
i=int
def g(x):
    a,b=str(x),i(len(str(x))/2)
    try:return(lambda d,c:i(d)+i(c)==10**len(d)-1 and x or g(i(d+c)-1))(a[:b],a[b:])
    except:return False
y=input();print((g(y)==y and True or g(y)))

```

**Amendment II**

Actually, now that I think of it, the user input should take less time when the output is `not True`:

```
y=input();z=g(y);print((z==y and True or z))

```

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


title: Food shortage in the Snakepit

text:
# Question
Title: Food shortage in the Snakepit
# Food shortage in the Snakepit

For the first time in 35 years, the snakepit is running out of food. The inhabitant snakes now have to fight each other in order to survive this food shortage. Only one snake can stand at the top of the food chain!

---

## Leaderboard

*Not here yet!*

*Last update on February, 24th*

Link to visualizations of last matches

---

## Description

If you want to fight for the last remaining apples/cherries/whatever, you have to provide a snake in form of a program that accepts a given input and returns its next move.

The only twist is that you're not alone in your pit. Another snake will try to get the rare food too! But it's dark inside the snakepit so you can only see yourself and the apple. Crashing into your opponent will result in your death, just like biting yourself or hitting a wall. Additionally, because apples are rare these days, you starve if your opponent ate enough to reach a length of 7.

The snakepit is a two-dimensional map with a width and height of 15, while the outermost tiles build an impassable wall:

```
  0 1 2 . . . c d e
0 # # # # # # # # #
1 #               #
2 #           x   #
. #               #
. #               #
. #               #
c #               #
d #               #
e # # # # # # # # #

```

Coordinates are zero-indexed, so the point where the `x` is would be `12,2`.

Your bot will be called with two arguments:

* The location of the food
* The locations of your body segments, separated by `/`

It should then write one of the following to stdout:

* `L` for a quarter left turn as its next move
* `R` for a quarter right turn
* Anything else for a move in the same direction

Example:

```
Projects/Snakepit> python bot.py 12,2 4,8/4,9/3,9/2,9
'R'
Projects/Snakepit>

```

---

## Rules

Your bot is allowed to:

* Output anything, because anything is a valid move
* Read/write files in its own directory which is located under ./snakes/ThisIsYourSnake
* Run on Ubuntu 14.04 and Windows 7 (it actually has to)

Your bot must not:

* Read/write files outside its own directory
* Use external resources such as the internet
* Have a runtime above 10 seconds per execution

You have to provide in your answer:

* The source code of the bot
* A bot/snake name
* (Your own name)
* A command to run your bot

> If you want to make my life easier, please provide a line like `CoolSnake MyOwnName python bot.py`.

---

## Scoring

Your snake gets a point for winning a game against another snake. A game is won under the following circumstances:

* Your opponent hits himself, you or a wall
* You reach length 7

Additionally, both snakes starve after 200 cycles.

Each snake will fight 10 matches for their survival against each other snake.

---

## Example Bots

Just to give you an idea, I'll provide these two (participating) example snakes:

**SneakySnake**

```
#!/usr/bin/env python

import sys, random

def main(food, me) :
    food = [int(i) for i in food.split(",")]
    me = [[int(i) for i in seg.split(",")] for seg in me.split("/")]
    head = me[0]
    v = [head[0] - me[1][0], head[1] - me[1][1]]

    if food[0] < head[0] :
        vn = [-1, 0]
    elif food[0] > head[0] :
        vn = [1, 0]
    elif food[0] == head[0] :
        if food[1] < head[1] :
            vn = [0, -1]
        elif food[1] > head[1] :
            vn = [0, 1]

    if v == vn :
        return "..."
    elif [-v[1], v[0]] == vn :
        return "R"
    elif [v[1], -v[0]] == vn :
        return "L"
    else :
        return random.choice(("R", "L"))

if __name__ == "__main__" :
    print main(*sys.argv[1:3])

```

> `SneakySnake Cipher python bot.py`

**ViciousViper**

```
#!/usr/bin/env python

import sys, random

def main(food, me) :
    food = [int(i) for i in food.split(",")]
    me = [[int(i) for i in seg.split(",")] for seg in me.split("/")]
    head = me[0]
    v = [head[0] - me[1][0], head[1] - me[1][1]]
    vn = [food[0] - head[0], food[1] - head[1]]
    if 0 not in vn :
        vn[v.index(0)-1] = 0
    vn[vn.index(0)-1] = vn[vn.index(0)-1] / abs(vn[vn.index(0)-1])

    if v == vn :
        return "..."
    elif [v[0] + vn[0], v[1] + vn[1]] == [0, 0] :
        return random.choice(("R", "L"))
    else :
        return "R" if [-v[1], v[0]] == vn else "L"

if __name__ == "__main__" :
    print main(*sys.argv[1:3])

```

> `ViciousViper Cipher python bot.py`

And their matches:

##

## Control program

You can find the control program on github, along with all bots and records of past matches.

**Requirements:**

* Python 2 + the libraries `numpy` and `pillow` (you can check if they are present via `python -c "import numpy, PIL"`, if it throws errors the modules are missing)
* Copying the full folder structure is required in order for the controller to work
* Register your bot(s) in the `./snakes/list.txt` file in the style of `CoolSnake MyOwnName Command To Run My Bot`
* Place your bot inside a directory with its name under `./snakes`
* Neither your, nor your bot's name is allowed to contain whitespaces!

**Usage:**

> `python run.py [-h] [-n int] [-s int] [-l int] [-c int] [-g]`

`python run.py` will run the tournament with all bots registered in list.txt and the standard properties. Advanced options are:

* `-h` displays a help message
* `-n int` rounds of battles for each combination of opponents
* `-s int` determines the size of the grid (width and height)
* `-l int` sets the required length to win
* `-c int` sets the limit of cycles
* `-g` or `--no-gifs` creates no gifs of the matches

# Answer
# Zen - C++

This Codémon is not here to eat but to fight. He knows that a dead enemy will not stole his apples.

---

`Name| Author |Launch with`

## `Zen GholGoth21 Zen.exe`

---

## Strategy

Everybody (excepted CircleOfLife) rush to the apples, but not Zen, not always. If the enemy can reach the food before him, he simply wait at the center (what? but what are you doing here, CircleOfLife?). Else, Zen goes at the apple and turns around while waiting that something happens. In fact, he uses the apple as a bait.

I didn't coded anything against the curious strategy of CircleOfLife because he can only win with very very much luck.

## The code

This is the complete code of the C++ project. Cut the 11 source files and the Makefile and compile with `make`

```
$ cat src/* Makefile
/*
 * @file    Enemy.cpp
 * @author  GholGoth21
 * @date    Créé le 1 mars 2015 à 14:10
 */

#include "Enemy.h"

#include <fstream>

Enemy::Enemy()
{
}

Enemy::~Enemy()
{
}

std::ostream &operator<<(std::ostream &os, const Enemy& e)
{
    return os<<e.m_pos<<" "<<e.m_date;
}

std::istream &operator>>(std::istream &is, Enemy& e)
{
    return is>>e.m_pos>>e.m_date;
}

int Enemy::distTo(int2 const &target, int date) const
{
    return m_pos.distTo(target)-(date-m_date);
}

bool Enemy::recentActivity(int2 const &pos, int date, int maxDelay) const
{
    return pos.distTo(m_pos)<=date-m_date && date-m_date<=maxDelay;
}
/*
 * @file    Enemy.h
 * @author  GholGoth21
 * @date    Créé le 1 mars 2015 à 14:10
 */

#ifndef ENEMY_H
#define ENEMY_H

#include "int2.h"

class Enemy
{
public:
    Enemy();
    virtual ~Enemy();

public:
    void setPos(int2 const &pos, int date) { m_pos=pos; m_date=date; }
    int distTo(int2 const &target, int date) const;
    int2 const &pos() const { return m_pos; }
    bool recentActivity(int2 const &pos, int date, int maxDelay) const;
    friend std::ostream &operator<<(std::ostream &os, const Enemy& e);
    friend std::istream &operator>>(std::istream &is, Enemy& e);

private:
    int2 m_pos;
    int m_date;
};

#endif  /* ENEMY_H */
/*
 * @file    Snake.cpp
 * @author  GholGoth21
 * @date    Créé le 28 février 2015 à 17:47
 */

#include "Snake.h"
#include "enums.h"
#include "StrManip.h"
#include "Enemy.h"

#include <vector>
#include <cmath>

Snake::Snake(std::string const &body)
{
    std::vector<std::string> posList;
    split(body, '/', posList);
    for(auto &pos : posList)
        m_body.push_back(int2(pos));
}

Snake::~Snake()
{
}

Command Snake::move(int2 food, int date, Enemy const &enemy)
{
    Command bestCommand[Command::count];

    int myDist=curPos().distTo(food);
    int enemyDist=enemy.distTo(food,date);

    if(myDist>=enemyDist && enemyDist>2)
    {
        orderCommand(int2(MAPSIZE/2,MAPSIZE/2), bestCommand);
        for(int i=0; i<Command::count; i++)
            if(validCommand(bestCommand[i]) && !enemy.recentActivity(nextPos(bestCommand[i]),date,5))
                return bestCommand[i];
    }
    if((myDist==1 && enemyDist>((len()-1)/2)*2+3) || enemyDist<-5)
    {
        orderCommand(food, bestCommand);
        for(int i=0; i<Command::count; i++)
            if(validCommand(bestCommand[i]))
                return bestCommand[i];
    }
    int2 embushPoint;
    int minDist=-1;
    foreach_enum(Direction, d)
    {
        int2 point(food+d.vector());
        int dist=point.quadDistTo(enemy.pos());
        if(dist<minDist || minDist<0)
        {
            minDist=dist;
            embushPoint=point;
        }
    }
    if(curPos().distTo(embushPoint)<enemy.distTo(embushPoint,date)-((len()-1)/2)*2)
    {
        int minimalAction=-1;
        int qMinDist = curPos().quadDistTo(embushPoint);
        Command minimalCommand;
        foreach_enum(Command, c)
        {
            int2 np=nextPos(c);
            int qDist = np.quadDistTo(embushPoint);
            if((qDist<minimalAction || minimalAction<0) && qDist>qMinDist && validCommand(c))
            {
                minimalAction=qDist;
                minimalCommand=c;
            }
        }
        return minimalCommand;
    }
    else
    {
        orderCommand(embushPoint, food, bestCommand);
        for(int i=0; i<Command::count; i++)
            if(validCommand(bestCommand[i]) && nextPos(bestCommand[i])!=food)
                return bestCommand[i];
    }

    return Command::forward;
}

bool Snake::validCommand(Command c) const
{
    if(!c.isValid())
        return false;
    int2 np = nextPos(c);
    if(!(0<np.x && np.x<MAPSIZE-1 && 0<np.y && np.y<MAPSIZE-1))
        return false;
    for(unsigned int i=2; i<m_body.size()-1; i++)
        if(np==m_body.at(i))
            return false;
    return true;
}

bool Snake::isStarting() const
{
    if(m_body.size()==3)
    {
        if(m_body.at(0)==int2(3,(MAPSIZE)/2) && m_body.at(1)==int2(2,(MAPSIZE)/2) && m_body.at(2)==int2(1,(MAPSIZE)/2))
            return true;
        else if(m_body.at(0)==int2(MAPSIZE-4,(MAPSIZE)/2) && m_body.at(1)==int2(MAPSIZE-3,(MAPSIZE)/2) && m_body.at(2)==int2(MAPSIZE-2,(MAPSIZE)/2))
            return true;
    }
    return false;
}

void Snake::orderCommand(int2 target, Command *tab)
{
    int weight[Command::count];
    foreach_enum(Command, c)
    {
        int2 np = nextPos(c);
        weight[c]=np.quadDistTo(target);
        tab[c]=c;
    }
    for(int i=0; i<Command::count-1; i++)
    {
        while(i>=0 && weight[tab[i]]>weight[tab[i+1]])
        {
            varSwitch(tab[i], tab[i+1]);
            i--;
        }
    }
}

void Snake::orderCommand(int2 target1, int2 target2, Command *tab)
{
    int weight[Command::count];
    foreach_enum(Command, c)
    {
        int2 np = nextPos(c);
        weight[c]=np.quadDistTo(target1)+np.quadDistTo(target2);
        tab[c]=c;
    }
    for(int i=0; i<Command::count-1; i++)
    {
        while(i>=0 && weight[tab[i]]>weight[tab[i+1]])
        {
            varSwitch(tab[i], tab[i+1]);
            i--;
        }
    }
}
/*
 * @file    Snake.h
 * @author  GholGoth21
 * @date    Créé le 28 février 2015 à 17:47
 */

#ifndef SNAKE_H
#define SNAKE_H

#include "int2.h"

#include <vector>

#define MAPSIZE 15

class Enemy;

class Snake
{
public:
    Snake(std::string const &body);
    virtual ~Snake();

public:
    Command move(int2 food, int date, Enemy const &enemy);
    Direction curDir() const { return (m_body.at(0)-m_body.at(1)).direction(); }
    int2 curPos() const { return m_body.at(0); }
    int2 nextPos(Command c) const { return curPos()+curDir().applyCommand(c).vector(); }
    bool validCommand(Command c) const;
    bool isStarting() const;
    void orderCommand(int2 target, Command *tab);
    void orderCommand(int2 target1, int2 target2, Command *tab);
    int len() const { return m_body.size(); }

private:
    std::vector<int2> m_body;
};

#endif  /* SNAKE_H */
/*
 * @file    StrManip.cpp
 * @author  GholGoth21
 * @date    Créé le 7 février 2015 à 17:26
 */

#include "StrManip.h"

#include <sstream>

std::vector<std::string> &split(const std::string &s, char delim, std::vector<std::string> &elems)
{
    std::stringstream ss(s);
    std::string item;
    while(std::getline(ss, item, delim))
        elems.push_back(item);
    return elems;
}

int atoi(std::string const &text)
{
    std::stringstream ss(text);
    int val;
    ss >> val;
    return val;
}
/*
 * @file    StrManip.h
 * @author  GholGoth21
 * @date    Créé le 7 février 2015 à 17:26
 */

#ifndef STRMANIP_H
#define STRMANIP_H

#include <string>
#include <vector>

std::vector<std::string> &split(const std::string &s, char delim, std::vector<std::string> &elems);
int atoi(std::string const &text);

#endif  /* STRMANIP_H */
/*
 * @file    enums.cpp
 * @author  GholGoth21
 * @date    Créé le 28 février 2015 à 17:55
 */

#include "enums.h"
#include "int2.h"

Command Direction::turnTo(Direction newDir) const
{
    if(!isValid() || !newDir.isValid())
        return Command::count; //Invalid
    else if((m_value==Direction::up && newDir==Direction::left) || (m_value==Direction::left && newDir==Direction::down) ||
            (m_value==Direction::down && newDir==Direction::right) || (m_value==Direction::right && newDir==Direction::up))
        return Command::left;
    else if((m_value==Direction::up && newDir==Direction::right) || (m_value==Direction::right && newDir==Direction::down) ||
            (m_value==Direction::down && newDir==Direction::left) || (m_value==Direction::left && newDir==Direction::up))
        return Command::right;
    else if(m_value==newDir)
        return Command::forward;
    else
        return Command::count; // Invalid
}

Direction Direction::applyCommand(Command c) const
{
    if(c==Command::forward)
        return m_value;
    else if(c==Command::left)
    {
        switch(m_value)
        {
            case Direction::left:
                return Direction::down;
            case Direction::up:
                return Direction::left;
            case Direction::right:
                return Direction::up;
            case Direction::down:
                return Direction::right;
            default:
                break;
        }
    }
    else if(c==Command::right)
    {
        switch(m_value)
        {
            case Direction::left:
                return Direction::up;
            case Direction::up:
                return Direction::right;
            case Direction::right:
                return Direction::down;
            case Direction::down:
                return Direction::left;
            default:
                break;
        }
    }
    return Direction::count; // Invalid
}

int2 Direction::vector() const
{
    switch(m_value)
    {
        case Direction::left:
            return int2(-1,0);
        case Direction::up:
            return int2(0,-1);
        case Direction::right:
            return int2(1,0);
        case Direction::down:
            return int2(0,1);
        default:
            return int2(0,0);
    }
}

std::ostream &operator<<(std::ostream &os, const Command& c)
{
    switch(c.m_value)
    {
        case Command::left:
            return os<<"L";
        case Command::right:
            return os<<"R";
        default:
            return os<<"F";
    }
}
/*
 * @file    enums.h
 * @author  GholGoth21
 * @date    Créé le 28 février 2015 à 17:55
 */

#ifndef ENUMS_H
#define ENUMS_H

#include <ostream>

struct int2;

#define DECL_ENUM_STRUCT(_name) \
_name() : m_value(static_cast<Type>(0)) {} \
_name(Type value) : m_value(value) {} \
_name(int value) : m_value(static_cast<Type>(value)) {} \
static Type begin() { return static_cast<Type>(0); } \
static Type end() { return count; } \
_name &operator++() { m_value=static_cast<Type>(static_cast<int>(m_value)+1); return *this; } \
operator int() const { return static_cast<Type>(m_value); } \
Type m_value;

#define foreach_enum(_type,_var) for(_type _var = _type::begin(); _var<_type::end(); ++_var)

struct Command
{
    enum Type
    {
        left,
        forward,
        right,
        count
    };

    bool isValid() const { return m_value<count; }
    friend std::ostream &operator<<(std::ostream &os, const Command& c);

    DECL_ENUM_STRUCT(Command)
};

struct Direction
{
    enum Type
    {
        left,
        up,
        right,
        down,
        count
    };

    bool isValid() const { return m_value<count; }
    Command turnTo(Direction newDir) const;
    Direction applyCommand(Command c) const;
    int2 vector() const;
    DECL_ENUM_STRUCT(Direction)
};

#endif  /* ENUMS_H */
/*
 * @file    int2.cpp
 * @author  GholGoth21
 * @date    Créé le 28 février 2015 à 17:37
 */

#include "int2.h"
#include "enums.h"
#include "StrManip.h"

#include <vector>
#include <cmath>

int2::int2()
{
}

int2::~int2()
{
}

int2::int2(std::string const &text)
{
    std::vector<std::string> posList;
    split(text, ',', posList);
    x=atoi(posList.at(0));
    y=atoi(posList.at(1));
}

Direction int2::direction() const
{
    if(x==0 && y==0)
        return Direction::count; // Invalid
    else if(y>=std::abs(x))
        return Direction::down;
    else if(x>=std::abs(y))
        return Direction::right;
    else if(x<=-std::abs(y))
        return Direction::left;
    else
        return Direction::up;
}

Direction int2::secondary() const
{
    if(x==0 || y==0)
        return Direction::count; //Invalid
    else if(y<=std::abs(x) && y>=0)
        return Direction::down;
    else if(x<=std::abs(y) && x>=0)
        return Direction::right;
    else if(x>=-std::abs(y) && x<=0)
        return Direction::left;
    else
        return Direction::up;
}

int int2::distTo(int2 const &other) const
{
    return std::abs(x-other.x)+std::abs(y-other.y);
}

int int2::quadDistTo(int2 const &other) const
{
    return sq(x-other.x)+sq(y-other.y);
}

int2 int2::operator+(int2 const &other) const
{
    return int2(x+other.x,y+other.y);
}

int2 int2::operator-(int2 const &other) const
{
    return int2(x-other.x,y-other.y);
}

std::ostream &operator<<(std::ostream &os, const int2& c)
{
    return os<<c.x<<","<<c.y;
}

std::istream &operator>>(std::istream &is, int2& c)
{
    std::string text;
    is>>text;
    c=int2(text);
    return is;
}
/*
 * @file    int2.h
 * @author  GholGoth21
 * @date    Créé le 28 février 2015 à 17:37
 */

#ifndef INT2_H
#define INT2_H

#include "enums.h"

#include <string>

struct int2
{
public:
    int2();
    int2(int p_x, int p_y) : x(p_x), y(p_y) {}
    int2(std::string const &text);
    virtual ~int2();

public:
    Direction direction() const;
    Direction secondary() const;
    int distTo(int2 const &other) const;
    int quadDistTo(int2 const &other) const;
    int2 operator+(int2 const &other) const;
    int2 operator-(int2 const &other) const;
    bool operator==(int2 const &other) const { return x==other.x && y==other.y; }
    bool operator!=(int2 const &other) const { return x!=other.x || y!=other.y; }
    friend std::ostream &operator<<(std::ostream &os, const int2& c);
    friend std::istream &operator>>(std::istream &is, int2& c);

public:
    int x;
    int y;
};

inline int sq(int val) { return val*val; }
template<typename T>
inline void varSwitch(T &a, T &b) { T tmp=a; a=b; b=tmp; }

#endif  /* INT2_H */
/*
 * @file    main.cpp
 * @author  GholGoth21
 * @date    Créé le 28 février 2015 à 17:23
 */

#include "int2.h"
#include "Snake.h"
#include "Enemy.h"

#include <cstdlib>
#include <iostream>
#include <fstream>

using namespace std;

/*
 * @brief La fonction principale du programme.
 * @param argc Le nombre de paramètres passés en ligne de commandes.
 * @param argv La liste des paramètres passés en ligne de commandes.
 */
int main(int argc, char** argv)
{
    /* Error handling */
    if(argc<3)
    {
        cerr<<"Error : not enough arguments on the command line."<<endl;
        cout<<"F"<<endl;
        return 1;
    }

    /* Init and load */
    int2 prevFood;
    int date = 0;
    Enemy enemy;
    ifstream load("PreviousState.txt");
    if(load)
    {
        load>>date;
        load>>prevFood;
        load>>enemy;
        load.close();
    }
    int2 food(argv[1]);
    Snake me(argv[2]);
    if(me.isStarting())
    {
        date=0;
        if(me.curPos().x<MAPSIZE/2)
            enemy.setPos(int2(MAPSIZE-4,MAPSIZE/2), 0);
        else
            enemy.setPos(int2(3,MAPSIZE/2), 0);
    }
    else if(prevFood!=food && me.curPos()!=prevFood)
    {
        enemy.setPos(prevFood, date);
    }

    /* Moving */
    cout<<me.move(food,date,enemy)<<endl;

    /* Saving */
    ofstream save("PreviousState.txt");
    if(save)
    {
        save<<++date<<endl;
        save<<food<<endl;
        save<<enemy<<endl;
        save.close();
    }
    return 0;
}
# Makefile
HEADERS = $(wildcard $(SRCPATH)/*.h)
SOURCES = $(wildcard $(SRCPATH)/*.cpp)
OBJECTS = $(patsubst $(SRCPATH)/%.cpp,$(BUILDPATH)/%.o,$(SOURCES))
M = Makefile

CFLAGS = -Wall -std=c++11

BINPATH = bin
BUILDPATH = build
SRCPATH = src

ifeq ($(OS),Windows_NT)
EXE = Zen.exe
else
EXE = Zen
endif

$(BINPATH)/$(EXE): $(BINPATH) $(BUILDPATH) $(OBJECTS)
    g++ -o $@ $(OBJECTS)

$(BUILDPATH)/%.o: $(SRCPATH)/%.cpp $(HEADERS) $M
    g++ $(CFLAGS) -o $@ -c $<

$(BINPATH) $(BUILDPATH):
    mkdir $@

clean:
    rm $(OBJECTS)

```

Or download the zip file : Zen.zip

## Results

```
|     Name     |   Master   | Score |
|--------------|------------|-------|
| Zen          | GholGoth21 | 24    |
| SneakySnake  | Cipher     | 10    |
| ViciousViper | Cipher     | 6     |
| CircleOfLife | Manu       | 4     |

```

And some typical battles (ViciousViper vs Zen and SneakySnake vs Zen) :

**Edit** : I add this very intersting battle against CircleOfLife :
> 6 votes

# Answer
## CircleOfLife (Java)

`CircleOfLife Manu java CircleOfLife` (Compile with `javac CircleOfLife.java`)

Runs towards the middle and stays there. I hope that some submissions will crash into it on their way to the food.

```
import java.awt.Point;
import java.util.ArrayList;
import java.util.List;

public class CircleOfLife {
    private static final int UP = 0;
    private static final int DOWN = 1;
    private static final int LEFT = 2;
    private static final int RIGHT = 3;
    private static final String GO_RIGHT = "R";
    private static final String GO_LEFT = "L";
    private static final String GO_FORWARD = "F";
    private static int currentDirection = UP;
    private static List<Point> snakeParts = new ArrayList<>();

    public static void main(String[] args) {
        String[] parts = args[1].split("/");
        for (String part : parts) {
            String[] pos = part.split(",");
            int x = Integer.parseInt(pos[0]);
            int y = Integer.parseInt(pos[1]);
            snakeParts.add(new Point(x,y));
        }
        Point head = snakeParts.get(0);
        Point neck = snakeParts.get(1);
        if (head.y - neck.y == 1) {
            currentDirection = DOWN;
        } else if (head.x - neck.x == -1) {
            currentDirection = LEFT;
        } else if (head.x - neck.x == 1) {
            currentDirection = RIGHT;
        }
        if (isInMiddle(head)) {
            makeCircle();
        } else {
            runToMiddle();
        }
    }

    private static void makeCircle() {
        if (!isInMiddle(snakeParts.get(1))) {
            System.out.println(GO_FORWARD);
            return;
        }
        Point head = snakeParts.get(0);
        Point neck = snakeParts.get(1);
        String output = GO_FORWARD;
        if (head.x == 8 && neck.x == 8) {
            output = currentDirection == UP ? GO_LEFT : GO_RIGHT;
        } else if (head.x == 7 && neck.x == 7) {
            output = currentDirection == UP ? GO_RIGHT : GO_LEFT;
        } else if (head.y == 8 && neck.y == 8) {
            output = currentDirection == RIGHT ? GO_LEFT : GO_RIGHT;
        } else if (head.y == 7 && neck.y == 7) {
            output = currentDirection == RIGHT ? GO_RIGHT : GO_LEFT;
        }
        System.out.println(output);
    }

    private static void runToMiddle() {
        Point head = snakeParts.get(0);
        int dX = 8 - head.x;
        int dY = 8 - head.y;
        String output = GO_FORWARD;

        if (Math.abs(dX) > Math.abs(dY)) {
            switch (currentDirection) {
                case DOWN: output = dX < 0 ? GO_RIGHT : GO_LEFT; break;
                case UP: output = dX < 0 ? GO_LEFT : GO_RIGHT; break;
                case RIGHT: output = dX < 0 ? GO_RIGHT : GO_FORWARD; break;
                case LEFT: output = dX < 0 ? GO_FORWARD : GO_RIGHT; break;
            }
        } else {
            switch (currentDirection) {
                case DOWN: output = dY < 0 ? GO_RIGHT : GO_FORWARD; break;
                case UP: output = dY < 0 ? GO_FORWARD : GO_RIGHT; break;
                case RIGHT: output = dY < 0 ? GO_LEFT : GO_RIGHT; break;
                case LEFT: output = dY < 0 ? GO_RIGHT : GO_LEFT; break;
            }
        }
        System.out.println(output);
    }

    public static boolean isInMiddle(Point snakePart) {
        if ((snakePart.x == 7 || snakePart.x == 8) &&
                (snakePart.y == 7 || snakePart.y == 8)) {
            return true;
        }
        return false;
    }
}

```
> 4 votes

---
Tags: game, king-of-the-hill, path-finding, grid
---


title: Analyzing Collatz-like sequences

text:
# Question
Title: Analyzing Collatz-like sequences
We define a Collatz-like sequence `s` with 4 positive integers:

* `n` starting value
* `d > 1` divisor
* `m > 1` multiplier
* `i` increment

(In the original Collatz sequence `d = 2` `m = 3` and `i = 1`.)

Given these integers `s` will be created in the following manner:

* `s(0) = n`
* if `k > 0` and `s(k-1) mod d = 0` then `s(k) = s(k-1) / d`
* if `k > 0` and `s(k-1) mod d != 0` then `s(k) = s(k-1) * m + i`

An example sequence with `d = 2, m = 3, i = 5` and `n = 80` will be `s = 80, 40, 20, 10, 5, 20, 10, 5, 20, ...`.

Every sequence will either reach higher values than any given bound (i.e. the sequence is divergent) or get into an infinite loop if for some `t` and `u` (`t!=u`) the `s(t) = s(u)` equality will be true.

In our problem if the value of a sequence element is larger than `10^9` or there is no element repetition before the `1000`th element the sequence is considered divergent.

## The task

You should write a program or function which takes the positive integers `d` `m` and `i` as inputs and outputs all the different ending types of the sequences (infinite loops and divergence) which the starting values `n = 1, 2, 3, ... 999, 1000` can produce.

## Input details

* The input is a string or list (or closest equivalent in your language) representing (in the common way) three positive integers `d`, `m` and `i` in that order. `d` and `m` are at least `2`. Neither number is larger than `100`.

## Output details

*The output specification is a bit wordy. Might worth to check out the examples first.*

* You should output to the standard output (or closest alternative) or return a string.
* If divergent sequence is possible the first line should be `DIVERGENT`.
* A unique representation of a sequence's loop is it's rotation where the smallest number is the last separated by spaces. E.g. if `s = 2 1 4 2 1 4 2 1` the loop is `4 2 1`.
* In every following line you should output every unique loop exactly once preceded by the word `LOOP`. E.g. `LOOP 4 2 1`
* The loops should be in ascending order in regard of their last element.
* Trailing newline is optional.

## Examples:

The first lines are the inputs and the following ones until a blank line are the outputs.

```
2 3 1
LOOP 4 2 1

2 2 6
LOOP 8 4 2 1
LOOP 12 6 3

3 7 8
DIVERGENT
LOOP 15 5 43 309 103 729 243 81 27 9 3 1
LOOP 22 162 54 18 6 2
LOOP 36 12 4

3 9 1
DIVERGENT

6 9 9
DIVERGENT
LOOP 18 3 36 6 1
LOOP 27 252 42 7 72 12 2
LOOP 45 414 69 630 105 954 159 1440 240 40 369 3330 555 5004 834 139 1260 210 35 324 54 9 90 15 144 24 4
LOOP 81 738 123 1116 186 31 288 48 8
LOOP 99 900 150 25 234 39 360 60 10
LOOP 126 21 198 33 306 51 468 78 13

10 10 10
LOOP 20 2 30 3 40 4 50 5 60 6 70 7 80 8 90 9 100 10 1

93 91 92
DIVERGENT
LOOP 2185 198927 2139 23
LOOP 4278 46

```

Reference implementation in Python 3 on Ideone.

This is code-golf so shortest entry wins.

# Answer
# Python 3, ~~269~~ ~~254~~ ~~252~~ 246 bytes

```
d,m,i=eval(input())
S=set()
for n in range(1,1001):
 T=X=()
 while len(T)**3<1e9>=n:
  T=(n,)+T;n=[n//d,n*m+i][n%d>0]
  if n in T:I=T.index;L=T[:I(n)+1];M=I(min(L));X=L[M:]+L[:M]
 S|={X}
for x in sorted(S):print(x and"LOOP"or"DIVERGENT",*x[::-1])

```

*(Now 10 times slower to save a few bytes. Typical code golf.)*

Input a list via STDIN (e.g. `[2, 3, 1]`). I'm thinking that there's got to be a better way of standardising the cycles...

The approach is quite straightforward — test all 1000 numbers and take only the unique outputs. However, there are two little tricks in there:

* Loops are represented by nonempty tuples, but more importantly divergence is represented by an *empty* tuple. This is good because:

+ It doesn't break `sorted`, and will even appear *before* all the loop tuples
    + It allows us to select a string via `x and"LOOP"or"DIVERGENT"`
    + `*()[::-1]` doesn't affect `print`
* The loops are built backwards to turn "sort ascending by last element" into "sort ascending by first element", which removes the need to pass a lambda into `sorted`.

## Previous submission, 252 bytes

```
d,m,i=eval(input())
def f(n,T=()):
 x=[n//d,n*m+i][n%d>0];I=T.index
 if x in T:L=T[:I(x)+1];M=I(min(L));return L[M:]+L[:M]
 return()if(T[1000:]or x>1e9)else f(x,(x,)+T)
for x in sorted(set(map(f,range(1,1001)))):print(x and"LOOP"or"DIVERGENT",*x[::-1])

```

This one's a lot faster.
> 7 votes

---
Tags: code-golf, math, number, sequence
---


title: The minimum fibonacci challenge!

text:
# Question
Title: The minimum fibonacci challenge!
## Challenge

> In this task you would be given an integer N (less than 106), find the minimum way in which you could sum to N using only Fibonacci numbers - this partition is called Zeckendorf representation.

You could use any Fibonacci number more than once and if there is more than one representation output any.

For example if the input is **67** then one possible output could be using the Fibonacci numbers **1,3,8,55** which is also the minimum number of Fibonacci numbers that could be used to get the sum **67**.

The input N is given on a single line, the inputs are terminated by EOF.

**Examples**

Given in the format `input: output`

```
0: 0
47: 34+13
3788: 2584+987+144+55+13+5
1646: 1597+34+13+2
25347: 17711+6765+610+233+21+5+2
677: 610+55+8+3+1
343: 233+89+21
3434: 2584+610+233+5+2

```

**Constraints**

* The number of inputs would not exceed 106 values.
* Your program should not run more than 5 seconds for all inputs.
* You can use any language of your choice.
* Shortest solution wins!

# Answer
> 16 votes
## Motorola 68000 assembly - 34 bytes

*(GNU assembler syntax)*

```
| short min_fib_partition(long N asm("%d2"), long *out asm("%a0"))
min_fib_partition:
    | Generate Fibonacci numbers on the stack (-1, 1, 0, 1, 1, 2, 3, ..., 1134903170).
    moveq #-1, %d0          | A = -1
    moveq #1, %d1           | B = 1
generate_loop:
    move.l %d0, -(%sp)      | Push A to the stack.
    exg.l %d0, %d1          | A' = B
    add.l %d0, %d1          | B' = A + B
    bvc.s generate_loop     | Stop when signed long overflows.

    | Go back up the stack, partitioning N using the greedy algorithm.
    moveq #0, %d0           | Initialize return value (number of terms).
subtract_loop:
    move.l (%sp)+, %d1      | Pop a Fibonacci number F off the stack.
    cmp.l %d1, %d2          | If N < F, continue to smaller Fibonacci number.
    blt.s subtract_loop
    addq.w #1, %d0          | Increment the term count.
    move.l %d1, (%a0)+      | Append F to the output array.
    sub.l %d1, %d2          | N -= F
    bne.s subtract_loop     | Continue if N has not yet reached zero.

    | Clear the stack by searching for that -1.
clear_stack_loop:
    tst.l (%sp)+
    bge clear_stack_loop

done:
    rts

```

**36 → 34:** Made Fibonacci generator stop on overflow rather than by counting, and fixed the `0` case so it outputs `[0]` rather than `[]`. However, passing a negative `N` crashes now.

The comment at the top is the C prototype of this function, using a language extension to identify what parameters go where (by default, they go on the stack).

My TI-89, with its 10MHz processor, takes 5 minutes to run this function on 1 – 1,000,000.

Although the machine code is (currently) fewer bytes than the GolfScript solution, it would probably be unfair to accept this as the shortest solution because:

If you have a TI-89/92/V200, you can download the full project here (outdated):

https://rapidshare.com/files/154945328/minfib.zip

Good luck coaxing RapidShare to give you the actual file. Does anyone know of a good host for files this big? 8940 is an awful lot of bytes.

# Answer
> 5 votes
## Golfscript, 43 chars

```
~]{:|': '[{0 1{|>!}{.@+}/;|1$-:|}do]'+'*n}%

```

I think this can probably be reduced by 3 to 5 chars with more effort. E.g. the unfold to then throw away the array feels wasteful.

# Answer
> 5 votes
## Javascript (142)

Only handles single input at a time. Because multi-line input is useless for JavaScript.

```
k=n=prompt(f=[a=b=1])|0;while((b=a+(a=b))<n)f.push(b);for(i=f.length,g=[];i--;)if(f[i]<=k)g.push(f[i]),k-=f[i];alert(n+': '+(n?g.join('+'):0))

```

http://jsfiddle.net/EqMXQ/

# Answer
> 5 votes
# C, 244 characters

```
#define P printf
int f[30];int main(){f[28]=f[29]=1;int i=28;for(;i>0;--i)f[i-1]=f[i+1]+f[i];int x;while(scanf("%i",&x)!=-1){P(x?"%i: ":"0: 0\n",x);if(x>0){int i=0,a=0;while(x>0){while(f[i]>x)++i;if(a++)P("+");P("%i",f[i]);x-=f[i];}P("\n");}}}

```

With whitespace:

```
#define P printf
int f[30];
int main(){
    f[28] = f[29] = 1;
    int i = 28;
    for(; i > 0; --i) f[i-1] = f[i+1] + f[i];
    int x;
    while(scanf("%i",&x) != -1) {
        P(x ? "%i: " : "0: 0\n",x);
        if(x > 0) {
            int i = 0, a = 0;
            while(x > 0) {
                while(f[i] > x) ++i;
                if(a++) P("+");
                P("%i",f[i]);
                x -= f[i];
            }
            P("\n");
        }
    }
}

```

This program will read numbers out of standard input and write to standard output.

# Answer
> 3 votes
## F# - 282 252 241 characters

```
let mutable d=int(stdin.ReadLine())
let q=d
let rec f x=if x<2 then 1 else f(x-2)+f(x-1)
let s x=
 d<-d-x
 x
printf"%d: %s"q (Core.string.Join("+",[for i in List.filter(fun x->x<d)[for i in 28..-1..0->f i]do if d-i>=0 then yield s i]))

```

# Answer
> 3 votes
## Python - 183 Chars

Majority of the code is handling multiple inputs :(

```
f=lambda a,b,n:b>n and a or f(b,a+b,n)
g=lambda n:n>0and"%d+%s"%(f(0,1,n),g(n-f(0,1,n)))or""
try:
 while 1:
  n=input()
  print "%d: %s"%(n,n<1and"0"or g(n).strip("+"))
except:0

```

# Answer
> 2 votes
# Mathematica 88

```
n = RandomInteger[10000, 10];

Print[k=#,For[i=99;l={},k>0,If[#<=k,k-=#;l~AppendTo~#]&@Fibonacci@i--];":"l~Row~"+"]&/@n

```

Example of output

```
3999: 2584+987+377+34+13+3+1
9226: 6765+1597+610+233+21
7225: 6765+377+55+21+5+2
9641: 6765+2584+233+55+3+1
6306: 4181+1597+377+144+5+2
4507: 4181+233+89+3+1
8848: 6765+1597+377+89+13+5+2
6263: 4181+1597+377+89+13+5+1
2034: 1597+377+55+5
6937: 6765+144+21+5+2

```

# Answer
> 2 votes
EXCEL : 89 chars in unique code:

# Answer
> 1 votes
**Scala - 353 chars** (100 chars for handling multiple inputs)

```
def h(m:Int){lazy val f={def g(a:Int,b:Int):Stream[Int]=a #:: g(b,a+b);g(0,1);};if(m==0)println(m+": "+m)else{var s=0;var t= f.takeWhile(_ <= m);var w="";while(s!= m){s+=t.last;w+=t.last+"+";t=t.takeWhile(_<=m-s);};println(m+": "+w.take(w.length-1))}}
Iterator.continually(Console.readLine).takeWhile(_ != "").foreach(line => h(Integer.parseInt(line)))

```

# Answer
> 1 votes
# Python 3 (170 chars)

```
while 1:
 s=input()
 if not s:break
 s=n=int(s);f=[1];t=[]
 while f[-1]<n:f+=[sum(f[-2:])]
 for i in f[::-1]:
  if s>=i:s-=i;t+=[i]
 print(n,'=','+'.join(map(str,t))or 0)

```

Multiline input, stop on empty line

# Answer
> 1 votes
# C, 151 characters

```
main() {int i=1,n,f[30]={1,1};for(;i++<30;)f[i]=f[i-1]+f[i-2];while(scanf("%d",&n))for(i=30;;--i)if(f[i]<=n){printf("%d\n",f[i]);if(!(n-=f[i]))break;}}

```

readable version:

```
main() {
    int i=1,n,f[30]={1,1};
    for(;i++<30;)f[i]=f[i-1]+f[i-2];
    while(scanf("%d",&n))
        for(i=30;;--i)
            if(f[i]<=n) {
                printf("%d\n",f[i]);
                if (!(n-=f[i])) break;
            }
}

```

# Answer
> 1 votes
# R, 170

```
x=scan();Filter(function(i)cat(unlist(Map(function(d)if(i>=d&&i){i<<-i-d;d},rev(lapply(Reduce(function(f,x)c(f[2],sum(f)),1:94,c(0,1),F,T),head,n=1)))),sep='+',fill=T),x)

```

Handles multiple inputs and cat's the result to STDOUT

```
> x=scan();Filter(function(i)cat(unlist(Map(function(d)if(i>=d&&i){i<<-i-d;d},rev(lapply(Reduce(function(f,x)c(f[2],sum(f)),1:94,c(0,1),F,T),head,n=1)))),sep='+',fill=T),x)
1: 100
2: 200
3: 300
4:
Read 3 items
89+8+3
144+55+1
233+55+8+3+1
numeric(0)
>

```

# Answer
> 1 votes
# R (460 chars)

Another version using R.
Reading from file "input", output to the file "output"

```
d=as.list(as.integer(scan("input","",sep="\n")));n=36;f=rep(1,n);for(i in 3:n){f[i]=f[i-2]+f[i-1]};d2=lapply(d,function(x){a=vector("integer");i=1;while(x>0){id=which(f>=x)[1];if(x==f[id]){x=x-f[id];a[i]=f[id]}else{x=x-f[id-1];a[i]=f[id-1]}i=i+1}a});d=mapply(c,d,d2,SIMPLIFY=0);for(i in 1:length(d)){t=d[[i]];l=length(t);if(l==1){d[[i]]=paste(t[1],t[1],sep=": ")}else{d[[i]]=paste(t[1],": ",paste(t[2:l],collapse="+"),sep="")}}lapply(d,write,"output",append=1)

```

"input" example

```
0
47
3788
1646
25347
677
343
3434

```

"output" example

```
0: 0
47: 34+13
3788: 2584+987+144+55+13+5
1646: 1597+34+13+2
25347: 17711+6765+610+233+21+5+2
677: 610+55+8+3+1
343: 233+89+21
3434: 2584+610+233+5+2

```

More readable version:

```
dt <- as.list(as.integer(scan(file = "input", what = "", sep = "\n")))
n <- 36
fib <- rep(1, n)
for(i in 3:n){fib[i] <- fib[i-2] + fib[i-1]}
dt2 <- lapply(dt, function(x){answ <- vector(mode = "integer")
                               i <- 1
                               while(x > 0){
                                   idx <- which(fib>=x)[1]
                                   if(x == fib[idx]){
                                       x <- x - fib[idx]
                                       answ[i] <- fib[idx]
                                   }
                                   else {
                                       x <- x - fib[idx-1]
                                       answ[i] <- fib[idx-1]
                                   }
                                   i <- i + 1
                               }
                               answ})
dt <- mapply(FUN = c, dt, dt2, SIMPLIFY = FALSE)
for(i in 1:length(dt)){
    t1 <- dt[[i]]
    t1.len <- length(t1)
    if(t1.len == 1){
        dt[[i]] <- paste(t1[1], t1[1], sep=": ")
    } else {
        dt[[i]] <- paste(t1[1], ": ", paste(t1[2:t1.len], collapse = "+"), sep="")
    }
}
lapply(dt, write, "output", append=TRUE)

```

# Answer
> 0 votes
## D (196 chars)

Run with `rdmd --eval=…`. This conveniently hides the boilerplate of `import x, y, z;` and `void main() {…}`:

```
int f(int i){return i-->1?f(i--)+f(i):i+2;}int n;foreach(x;std.stdio.stdin.byLine.map!(to!int))writeln(x,": ",x?n=x,reduce!((r,i)=>f(i)<=n?n-=f(i),r~="+"~f(i).text:r)("",29.iota.retro)[1..$]:"0")

```

# Answer
> 0 votes
**Using Java**

```
package org.mindcraft;

import java.util.Scanner;

public class Fibbo {
    public static void main(String[] args) {
    String number = null;
    int tmp, sum;
    int i = 1, j = 1;
    Scanner in = new Scanner(System.in);
    number = in.nextLine();
    String[] arr = number.split(" ");
    for (int it = 0; it < arr.length; it++) {
        tmp = Integer.parseInt(arr[it]);
        String value = tmp+" : ";
        while (tmp > 0) {
            i = 1;
            j = 1;
            for (int k = 0; k < 10000; k++) {
                sum = i + j;
                if (sum > tmp) {
                    //if (value == null) {
                    char ch=value.charAt(value.length()-2);
                    if(ch==':')
                    {
                        value = value+" "+ j + "";
                    } else {
                        value = value + " + " + j;
                    }

                    tmp = tmp - j;
                    break;
                }
                i = j;
                j = sum;
            }
        }
        System.out.println(value);
    }
}
}

```

---
Tags: code-golf, fibonacci, integer-partitions
---