# Question
Title: Solitaire Dreams - Creating a winnable solitaire starting hand
It's me. Cave Johnson.

It's May 21st. You are working at Aperture Science, finest company on Earth, and tomorrow we're releasing Version 3.0 of our flagship windowing system (or *WindowS*): CavOS. Unfortunately, tomorrow morning, our chief competitor is releasing Version 3.0 of their *WindowS* too!

It's been leaked to me, Cave Johnson, CEO that the competing *WindowS* has one feature that CavOS lacks: A game of Klondike Solitaire. I, Cave Johnson, am concerned that this omission will lead to drastically lower sales. As such, I, Cave Johnson, have devised a competition between the programming interns to create a game of Solitaire. The programmer whose entry is chosen will get the opportunity to join the exciting GlaDOS AI project.

I, Cave Johnson, has a few requirements:

* Due to the fact that the Software must ship tomorrow, the **shortest program will be chosen** such that it can fit in the spare sectors of the already printed, imaged floppies.
* Don't worry about the gameplay. Our customers have printers don't they? All I need is for your program to **produce a list showing: The order of the cards in the deck, and the contents of each of the 7 piles. The deck will be dealt from the top. The piles will be visible from the bottom. Use the abbreviations H, D, C, S for Hearts, Diamonds, Clubs and Spades. Use the abbreviations K, Q, J, A for King, Queen, Jack, and Ace. Each card should be separated by a space. The first line should show the deck, the second the card of the first and smallest pile, the third the cards of the second pile and so on.** You are welcome to use T instead of 10 if you wish.
* We're making lemonade here - not sucking lemons. I, Cave Johnson, don't like losing, and neither do our customers. **Every game must be winnable**
* **The game must be randomised.** No attempting to encode a single game. There are 7000 trillion possible Klondike hands, and about 90% of them are winnable. I'd be happy with a program that can produce 256 or more different hands. If your language lacks a manner to get random numbers (from a timer or the like), then assume that you can get a seed in a manner appropriate for your language.
* Our customers are reasonably clever. **Assume for winnability that they're playing Draw 3, with no limits on times through the deck**

On behalf of everybody (and everything) at Aperture, I wish you all good luck. We're counting on you.

"*Caroline? How do I shut this damn thing off?*"

---

Out of character: assume the rules of Windows, Draw 3, Not-vegas solitaire. I've attempted to cross every t and dot every i, but ask if you've any questions. Good luck.

Example output:

```
5H AS 7C 8S QH ...
AH
JS 10S
JC JH 7C
9D AC 8D 7C
.
.
.

```

# Answer
> 11 votes
# Brainfuck - 1575 1365

I am horribly abusing the minimum number of unique deals. This will produce exactly 256 distinct outputs. It accepts one byte of input as its random seed.

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

```

Could definitely be condensed more, but that is kinda the nature of the language. This is quick and dirty, and it works.

Example output (input = 98):

```
8H 9S KS KH KD KC QS QH QD QC JS JH JD JC TS TH TD TC 9H 9D 9C 8S 8D 8C
AC
2C 3C
4C 5C 6C
7C AD 2D 3D
4D 5D 6D 7D AH
2H 3H 4H 5H 6H 7H
AS 2S 3S 4S 5S 6S 7S

```

It is fairly intuitive that all decks of this format are winnable.

---
Tags: code-golf, game
---


title: Emulate an Intel 8086... COMPLETELY

text:
# Question
Title: Emulate an Intel 8086... COMPLETELY
> **Possible Duplicate:**
> Emulate an Intel 8086 CPU

I know that there already is a code golf for this, but that one didn't require much. This one, however, is for masochists only! \>:) OK, you need to emulate an entire 8086, every single opcode. Not every flag needs to be computed, but every single documented opcode needs to be implemented.

However, that's just the beginning. I STRONGLY encourage you to support more than just this. NEC V20? Why not? Soviet clones? Don't mind if I do.

For some help, opcodes 0x60 - 0x6F are just aliases for opcodes 0x70 - 0x7F on the 8086 and 8088 ONLY. If you ask the guy who runs reenigne.org, he'll say the same thing, simply because it's been proven by hardware tests, on an IBM XT.

Anyways, for bonus points, emulate an entire V20, 286, or 386, no facets left unemulated.

# Answer
> 4 votes
# C++ - 5084 lines

github.com/Alegend45/IBM5150/blob/master/cpu.h

This emulates the entire 8086, the 80186 instruction set, and part of the NEC V20. This took me over 3 weeks.

---
Tags: code-challenge
---


title: Drawing a gradient in ASCII art

text:
# Question
Title: Drawing a gradient in ASCII art
**Task description:**

Write a program as short as possible to draw a radial gradient in ASCII art. The size of the output grid is predefined. The center point and the characters to be used for the gradient are provided as input to the program.

The gradient will be 70×25 character cells in size with the following specifications

* The upper-left corner of the grid has the coordinates (0, 0).
* The gradient, consisting of the characters provided, is mapped into 35 *length units*. A length unit is one character tall and two characters wide (since `monospaced fonts` usually have characters twice as high as they are wide).
* Within those 35 LU the current distance from the center point is multiplied by number of gradient characters/35 to get the index of the character to draw at that point. Fractional numbers for the index are rounded towards zero here. The length units are to be left as a real number. (Of course, if the results are the same, the implementation doesn't matter.)
* Beyond those 35 LU only the last gradient character appears. However, since the last gradient »band« already starts *within* the 35 LU, the last character starts appearing short of 35 LU already.

**Input:**

The input is given on standard input and consists of three lines, each terminated by a line break:

* The *x* coordinate of the gradient center point
* The *y* coordinate of the gradient center point
* The characters to use for drawing the gradient. Those may include spaces.

**Output:**

Output is the gradient as defined by the rules above on standard output. The standard error stream is ignored. Each line of the gradient is terminated by a line break. No other characters except those defined by the input may occur.

**Sample input 1:**

```
58
14
 .:;+=xX$&

```

**Sample output 1:**

```
&&$$$$$$$$XXXXXXXXxxxxxxxxx===========++++++++++++++++++++++++++++++++
&$$$$$$$$XXXXXXXXxxxxxxxxx=========+++++++++++++;;;;;;;;;;;;;;;;;;;;;+
$$$$$$$$XXXXXXXXxxxxxxxx=========+++++++++++;;;;;;;;;;;;;;;;;;;;;;;;;;
$$$$$$$XXXXXXXXxxxxxxxx========++++++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
$$$$$$XXXXXXXXxxxxxxxx========+++++++++;;;;;;;;;;;;;:::::::::::::;;;;;
$$$$$XXXXXXXXxxxxxxxx=======+++++++++;;;;;;;;;;;:::::::::::::::::::::;
$$$$$XXXXXXXxxxxxxxx=======+++++++++;;;;;;;;;:::::::::::::::::::::::::
$$$$XXXXXXXXxxxxxxx=======++++++++;;;;;;;;;:::::::::::::::::::::::::::
$$$$XXXXXXXxxxxxxx========+++++++;;;;;;;;::::::::::...............::::
$$$XXXXXXXXxxxxxxx=======+++++++;;;;;;;;:::::::::...................::
$$$XXXXXXXxxxxxxx=======++++++++;;;;;;;::::::::.......................
$$$XXXXXXXxxxxxxx=======+++++++;;;;;;;::::::::.........       ........
$$$XXXXXXXxxxxxxx=======+++++++;;;;;;;:::::::........           ......
$$$XXXXXXXxxxxxxx=======+++++++;;;;;;;:::::::.......             .....
$$$XXXXXXXxxxxxxx=======+++++++;;;;;;;:::::::.......             .....
$$$XXXXXXXxxxxxxx=======+++++++;;;;;;;:::::::.......             .....
$$$XXXXXXXxxxxxxx=======+++++++;;;;;;;:::::::........           ......
$$$XXXXXXXxxxxxxx=======+++++++;;;;;;;::::::::.........       ........
$$$XXXXXXXxxxxxxx=======++++++++;;;;;;;::::::::.......................
$$$XXXXXXXXxxxxxxx=======+++++++;;;;;;;;:::::::::...................::
$$$$XXXXXXXxxxxxxx========+++++++;;;;;;;;::::::::::...............::::
$$$$XXXXXXXXxxxxxxx=======++++++++;;;;;;;;;:::::::::::::::::::::::::::
$$$$$XXXXXXXxxxxxxxx=======+++++++++;;;;;;;;;:::::::::::::::::::::::::
$$$$$XXXXXXXXxxxxxxxx=======+++++++++;;;;;;;;;;;:::::::::::::::::::::;
$$$$$$XXXXXXXXxxxxxxxx========+++++++++;;;;;;;;;;;;;:::::::::::::;;;;;

```

**Sample input 2:**

```
0
0
X.X.X.X

```

**Sample output 2:**

```
XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX
XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX
XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX
XXXXXXXX............XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX
XXXXXX.............XXXXXXXXXX...........XXXXXXXXXX..........XXXXXXXXXX
..................XXXXXXXXXXX..........XXXXXXXXXX...........XXXXXXXXXX
................XXXXXXXXXXXX...........XXXXXXXXXX..........XXXXXXXXXXX
...............XXXXXXXXXXXX...........XXXXXXXXXX...........XXXXXXXXXXX
............XXXXXXXXXXXXXX...........XXXXXXXXXXX..........XXXXXXXXXXXX
.........XXXXXXXXXXXXXXX............XXXXXXXXXXX...........XXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXX............XXXXXXXXXXX...........XXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXX.............XXXXXXXXXXX...........XXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..............XXXXXXXXXXXX...........XXXXXXXXXXXXXXX
XXXXXXXXXXXXXXX................XXXXXXXXXXXX............XXXXXXXXXXXXXXX
XXXXXXXXXXX..................XXXXXXXXXXXXX............XXXXXXXXXXXXXXXX
...........................XXXXXXXXXXXXX............XXXXXXXXXXXXXXXXXX
........................XXXXXXXXXXXXXXX............XXXXXXXXXXXXXXXXXXX
......................XXXXXXXXXXXXXXX.............XXXXXXXXXXXXXXXXXXXX
..................XXXXXXXXXXXXXXXXX.............XXXXXXXXXXXXXXXXXXXXXX
.............XXXXXXXXXXXXXXXXXXXX..............XXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...............XXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX...............XXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX.................XXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX...................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXX......................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

```

**Sample input 3:**

```
70
25
.:+#

```

**Sample output 3:**

```
######################################################++++++++++++++++
#################################################+++++++++++++++++++++
#############################################+++++++++++++++++++++++++
##########################################++++++++++++++++++++++++++++
#######################################+++++++++++++++++++++++++++++++
####################################++++++++++++++++++++++++++++++++++
##################################++++++++++++++++++++++++++++++++++++
################################++++++++++++++++++++++++++++++++++++++
##############################++++++++++++++++++++++++++++++++::::::::
#############################+++++++++++++++++++++++++++::::::::::::::
###########################+++++++++++++++++++++++++::::::::::::::::::
##########################++++++++++++++++++++++++::::::::::::::::::::
#########################++++++++++++++++++++++:::::::::::::::::::::::
########################+++++++++++++++++++++:::::::::::::::::::::::::
#######################++++++++++++++++++++:::::::::::::::::::::::::::
######################++++++++++++++++++++::::::::::::::::::::::::::::
#####################+++++++++++++++++++::::::::::::::::::::::::::::::
####################+++++++++++++++++++::::::::::::::::::::::::.......
####################++++++++++++++++++::::::::::::::::::::::..........
###################+++++++++++++++++++::::::::::::::::::::............
###################++++++++++++++++++:::::::::::::::::::..............
###################+++++++++++++++++:::::::::::::::::::...............
##################++++++++++++++++++::::::::::::::::::................
##################++++++++++++++++++:::::::::::::::::.................
##################++++++++++++++++++:::::::::::::::::.................

```

**Sample input 4**

```
59
1
 abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789<>|,.-#+!$%&/()=?*'_:;

```

**Sample output 4**

```
!+#-,|><87654210ZYWVUTRQPONLKJIHFEDCBzyxwutsrqonmlkjhgfedcbbbcdefghjkl
!+#-,|><87654210ZYWVUTRQPONLKJIHFEDCAzyxwutsrqonmljihgfdcba abcdfghijl
!+#-,|><87654210ZYWVUTRQPONLKJIHFEDCBzyxwutsrqonmlkjhgfedcbbbcdefghjkl
!+#-,|><97654310ZYXVUTSQPONMKJIHGEDCBAyxwvutrqponmkjihgffeedeeffghijkm
$+#-.|><98654320ZYXWUTSRQONMLKIHGFEDBAzyxwutsrqponmlkjihhggggghhijklmn
$!#-.,|<987643210YXWVUSRQPONLKJIHGEDCBAzywvutsrqponmllkjjjiiijjjkllmno
$!+#.,|><87654210ZYXVUTSRQONMLKJHGFEDCBAzywvutsrrqponnmmlllllllmmnnopq
%!+#-.|><987543210YXWVUTRQPONMLJIHGFEDCBAzyxwvutsrrqppooonnnnnoooppqrr
%$!+-.,|><87654310ZYXWVTSRQPONMLJIHGFEDCBAzyxxwvuttssrrqqqqqqqqqrrsstt
&%!+#-.,><987643210ZYXVUTSRQPONMLKJIHGFEDCBAzyyxwvvuutttssssssstttuuvv
&%$!+#.,|><986543210ZYWVUTSRQPONMLKJIHGFEDDCBAzzyyxwwwvvvuuuuuvvvwwwxy
/&%$!#-.,|><976543210ZYXVUTSRQPONMLKKJIHGFEEDCBBAAzzyyyxxxxxxxxxyyyzzA
(/&%!+#-.,|><876543210ZYXWVUTSRQPONMLKJJIHGGFEEDCCBBBAAAzzzzzzzAAABBBC
)(/%$!+#-.,|><876543210ZYXWVUTSRQPPONMLKKJIIHGGFFEEDDDCCCCCCCCCCCDDDEE
=)(&%$!+#-.,|><986543210ZYYXWVUTSRQPPONMMLKKJIIHHGGGFFFEEEEEEEEEFFFGGG
?=)(&%$!+#-.,|><9876543210ZYXWVVUTSRRQPOONMMLLKJJJIIIHHHHHHHHHHHHHIIIJ
*?=)(/%$!+#-.,|><98765432210ZYXWWVUTSSRQQPOONNMMLLLKKKJJJJJJJJJJJKKKLL
'*?=)(/&%$!+#-.,|><98765432110ZYXXWVUUTSSRRQPPOOONNNMMMMMLLLLLMMMMMNNN
_'*?=)(/&%$!+#-.,|><988765432210ZYYXWWVUUTTSSRRQQQPPPOOOOOOOOOOOOOPPPQ
:_'*?=)(/&%$!+##-.,|><9877654332100ZYYXXWVVUUTTTSSSRRRRQQQQQQQQQRRRRSS
;;:_'*?=)(/&%$!+#-.,,|><98876554322100ZZYYXXWWVVVUUUTTTTTTTTTTTTTTTUUU
;;;:_'*?=)(/&&%$!+#-.,,|><9987665443321100ZZYYYXXXWWWWVVVVVVVVVVVWWWWX
;;;;;:_'*?=)(/&%$$!+#-..,|>><9887665544322211000ZZZYYYYYYYYYYYYYYYYYZZ
;;;;;;:_'*??=)(/&%%$!+##-.,,|><<99877665544333222111100000000000001111
;;;;;;;;:_'*?==)(/&&%$!++#--.,,|>><<9887766655544433333322222223333334

```

A week has passed. It is time to unveil the solution lengths from our university's contest:

> 167 – Python
> 189 – Haskell
> 203 – C
> 210 – VB.NET
> 219 – C

And our own solutions:

> 91 – GolfScript
> 125 – Ruby
> 157 – PowerShell

# Answer
> 11 votes
## Ruby 1.9, ~~116 114 108~~ 101 characters

```
x,y,z=*$<;25.times{|r|70.times{|c|$><<z[[(c-x.to_i+2.i*(r-y.to_i)).abs/70.0*k=z=~/$/,k-1].min]};puts}

```

# Answer
> 31 votes
# Brainfuck - 1286

This is one of my favorite creations yet. Includes a working (for some definitions of working) square root function.

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

```

Output is a bit off due to rounding errors, but still recognizable. Floating point is beyond my current skill level. Unfortunately this will only work with 16 bit cells, which means it is going to be dog slow.

Output 1:

```
&$$$$$$$$XXXXXXXXxxxxxxxxxx========++++++++++++++++++++++;;;++++++++++
$$$$$$$$$XXXXXXxxxxxxxxxx========++++++++++++++;;;;;;;;;;;;;;;;;;;;;;;
$$$$$$$XXXXXXXXxxxxxxxx========++++++++++++;;;;;;;;;;;;;;;;;;;;;;;;;;;
$$$$$$$XXXXXXxxxxxxxxxx======++++++++++++;;;;;;;;;;;;;;;;:::;;;;;;;;;;
$$$$$XXXXXXXXxxxxxxxx========++++++++++;;;;;;;;;;:::::::::::::::::::;;
$$$$$XXXXXXxxxxxxxxxx======++++++++++;;;;;;;;:::::::::::::::::::::::::
$$$$$XXXXXXxxxxxxxx======++++++++++;;;;;;;;:::::::::::::::::::::::::::
$$$XXXXXXxxxxxxxxxx======++++++++;;;;;;;;::::::::::::::::...::::::::::
$$$XXXXXXxxxxxxxx========++++++++;;;;;;::::::::::::...............::::
$$$XXXXXXxxxxxxxx======++++++++;;;;;;;;::::::::::...................::
$$$XXXXXXxxxxxxxx======++++++++;;;;;;::::::::::..........   ..........
$$$XXXXXXxxxxxxxx======++++++++;;;;;;::::::::........           ......
$$$XXXXXXxxxxxxxx======++++++++;;;;;;::::::::......               ....
$$$XXXXXXxxxxxxxx======++++++++;;;;;;::::::::......               ....
$XXXXXXxxxxxxxx======++++++++;;;;;;::::::::......                   ..
$$$XXXXXXxxxxxxxx======++++++++;;;;;;::::::::......               ....
$$$XXXXXXxxxxxxxx======++++++++;;;;;;::::::::......               ....
$$$XXXXXXxxxxxxxx======++++++++;;;;;;::::::::........           ......
$$$XXXXXXxxxxxxxx======++++++++;;;;;;::::::::::..........   ..........
$$$XXXXXXxxxxxxxx======++++++++;;;;;;;;::::::::::...................::
$$$XXXXXXxxxxxxxx========++++++++;;;;;;::::::::::::...............::::
$$$XXXXXXxxxxxxxxxx======++++++++;;;;;;;;::::::::::::::::...::::::::::
$$$$$XXXXXXxxxxxxxx======++++++++++;;;;;;;;:::::::::::::::::::::::::::
$$$$$XXXXXXxxxxxxxxxx======++++++++++;;;;;;;;:::::::::::::::::::::::::
$$$$$XXXXXXXXxxxxxxxx========++++++++++;;;;;;;;;;:::::::::::::::::::;;

```

Output 2:

```
XXXXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXX
XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX
XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX
XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX
XXXXXXXX............XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX
XX................XXXXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX
..................XXXXXXXXXX............XXXXXXXXXX..........XXXXXXXXXX
................XXXXXXXXXXXX..........XXXXXXXXXXXX..........XXXXXXXXXX
..............XXXXXXXXXXXX............XXXXXXXXXX..........XXXXXXXXXXXX
..........XXXXXXXXXXXXXXXX..........XXXXXXXXXXXX..........XXXXXXXXXXXX
..XXXXXXXXXXXXXXXXXXXXXX............XXXXXXXXXX............XXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX............XXXXXXXXXXXX..........XXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..............XXXXXXXXXX............XXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX................XXXXXXXXXXXX............XXXXXXXXXXXXXX
XXXXXXXXXXXX..................XXXXXXXXXXXX............XXXXXXXXXXXXXXXX
XX..........................XXXXXXXXXXXXXX..........XXXXXXXXXXXXXXXXXX
..........................XXXXXXXXXXXXXX............XXXXXXXXXXXXXXXXXX
......................XXXXXXXXXXXXXXXX............XXXXXXXXXXXXXXXXXXXX
..................XXXXXXXXXXXXXXXXXX..............XXXXXXXXXXXXXXXXXXXX
..............XXXXXXXXXXXXXXXXXXXX..............XXXXXXXXXXXXXXXXXXXXXX
..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..............XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX................XXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX..................XXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX....................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX......................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

```

# Answer
> 12 votes
## Python - 141 chars

```
x=input();y=input();z=raw_input();w=len(z)
for i in range(-y,25-y):print"".join(z[min(w-1,int((i*i*4+j*j)**.5*w/70))]for j in range(-x,70-x))

```

# Answer
> 8 votes
## Delphi, 200 (and 185)

Since I like ascii-art here a Delphi version of this code golf:

```
uses Math;var G:string;X,Y,l,i,j:Int16;begin ReadLn(X,Y);ReadLn(G);l:=Length(G);for j:=-y to 24-y do for i:=-x to 70-x do if i=70-x then WriteLn else Write(g[Min(l,1+Trunc(l*sqrt(i*i/4+j*j)/35))])end.

```

Not very impressive character-wise, as I had to use the Math unit to link in the Min() function. Also, ReadLn() somehow doesn't read integers and strings in one call, so that's quite expensive too. The newline needs a lot of characters too. Also, Delphi needs quite a lot of whitespace around it's keywords. Not very proud of this one.

Anyway, the output of sample 4 gives me :

```
!+#-,|><87654210ZYWVUTRQPONLKJIHFEDCBzyxwutsrqonmlkjhgfedcbbbcdefghjkl
!+#-,|><87654210ZYWVUTRQPONLKJIHFEDCAzyxwutsrqonmljihgfdcba abcdfghijl
!+#-,|><87654210ZYWVUTRQPONLKJIHFEDCBzyxwutsrqonmlkjhgfedcbbbcdefghjkl
!+#-,|><97654310ZYXVUTSQPONMKJIHGEDCBAyxwvutrqponmkjihgffeedeeffghijkm
$+#-.|><98654320ZYXWUTSRQONMLKIHGFEDBAzyxwutsrqponmlkjihhggggghhijklmn
$!#-.,|<987643210YXWVUSRQPONLKJIHGEDCBAzywvutsrqponmllkjjjiiijjjkllmno
$!+#.,|><87654210ZYXVUTSRQONMLKJHGFEDCBAzywvutsrrqponnmmlllllllmmnnopq
%!+#-.|><987543210YXWVUTRQPONMLJIHGFEDCBAzyxwvutsrrqppooonnnnnoooppqrr
%$!+-.,|><87654310ZYXWVTSRQPONMLJIHGFEDCBAzyxxwvuttssrrqqqqqqqqqrrsstt
&%!+#-.,><987643210ZYXVUTSRQPONMLKJIHGFEDCBAzyyxwvvuutttssssssstttuuvv
&%$!+#.,|><986543210ZYWVUTSRQPONMLKJIHGFEDDCBAzzyyxwwwvvvuuuuuvvvwwwxy
/&%$!#-.,|><976543210ZYXVUTSRQPONMLKKJIHGFEEDCBBAAzzyyyxxxxxxxxxyyyzzA
(/&%!+#-.,|><876543210ZYXWVUTSRQPONMLKJJIHGGFEEDCCBBBAAAzzzzzzzAAABBBC
)(/%$!+#-.,|><876543210ZYXWVUTSRQPPONMLKKJIIHGGFFEEDDDCCCCCCCCCCCDDDEE
=)(&%$!+#-.,|><986543210ZYYXWVUTSRQPPONMMLKKJIIHHGGGFFFEEEEEEEEEFFFGGG
?=)(&%$!+#-.,|><9876543210ZYXWVVUTSRRQPOONMMLLKJJJIIIHHHHHHHHHHHHHIIIJ
*?=)(/%$!+#-.,|><98765432210ZYXWWVUTSSRQQPOONNMMLLLKKKJJJJJJJJJJJKKKLL
'*?=)(/&%$!+#-.,|><98765432110ZYXXWVUUTSSRRQPPOOONNNMMMMMLLLLLMMMMMNNN
_'*?=)(/&%$!+#-.,|><988765432210ZYYXWWVUUTTSSRRQQQPPPOOOOOOOOOOOOOPPPQ
:_'*?=)(/&%$!+##-.,|><9877654332100ZYYXXWVVUUTTTSSSRRRRQQQQQQQQQRRRRSS
;;:_'*?=)(/&%$!+#-.,,|><98876554322100ZZYYXXWWVVVUUUTTTTTTTTTTTTTTTUUU
;;;:_'*?=)(/&&%$!+#-.,,|><9987665443321100ZZYYYXXXWWWWVVVVVVVVVVVWWWWX
;;;;;:_'*?=)(/&%$$!+#-..,|>><9887665544322211000ZZZYYYYYYYYYYYYYYYYYZZ
;;;;;;:_'*??=)(/&%%$!+##-.,,|><<99877665544333222111100000000000001111
;;;;;;;;:_'*?==)(/&&%$!++#--.,,|>><<9887766655544433333322222223333334

```

If you would accept indented output, this version is a bit shorter by changing the newline into an indent that leads to a 80-character wrap (simulating a newline on standard 80x25 consoles) :

```
uses Math;var G:string;X,Y,l,i,j:Int16;begin ReadLn(X,Y);ReadLn(G);l:=Length(G);for j:=-y to 24-y do for i:=-x to 70-x do Write(g[Min(l,1+Trunc(l*sqrt(i*i/4+j*j)/35))]:11*Ord(i=-x))end.

```

(this saves 15 characters, for a total of 185 characters). It's output for "0 0 X.X.X.X" is :

```
          XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX
          XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX
          XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX
          XXXXXXXX............XXXXXXXXXX..........XXXXXXXXXX..........XXXXXXXXXX
          XXXXXX.............XXXXXXXXXX...........XXXXXXXXXX..........XXXXXXXXXX
          ..................XXXXXXXXXXX..........XXXXXXXXXX...........XXXXXXXXXX
          ................XXXXXXXXXXXX...........XXXXXXXXXX..........XXXXXXXXXXX
          ...............XXXXXXXXXXXX...........XXXXXXXXXX...........XXXXXXXXXXX
          ............XXXXXXXXXXXXXX...........XXXXXXXXXXX..........XXXXXXXXXXXX
          .........XXXXXXXXXXXXXXX............XXXXXXXXXXX...........XXXXXXXXXXXX
          XXXXXXXXXXXXXXXXXXXXXXX............XXXXXXXXXXX...........XXXXXXXXXXXXX
          XXXXXXXXXXXXXXXXXXXXX.............XXXXXXXXXXX...........XXXXXXXXXXXXXX
          XXXXXXXXXXXXXXXXXX..............XXXXXXXXXXXX...........XXXXXXXXXXXXXXX
          XXXXXXXXXXXXXXX................XXXXXXXXXXXX............XXXXXXXXXXXXXXX
          XXXXXXXXXXX..................XXXXXXXXXXXXX............XXXXXXXXXXXXXXXX
          ...........................XXXXXXXXXXXXX............XXXXXXXXXXXXXXXXXX
          ........................XXXXXXXXXXXXXXX............XXXXXXXXXXXXXXXXXXX
          ......................XXXXXXXXXXXXXXX.............XXXXXXXXXXXXXXXXXXXX
          ..................XXXXXXXXXXXXXXXXX.............XXXXXXXXXXXXXXXXXXXXXX
          .............XXXXXXXXXXXXXXXXXXXX..............XXXXXXXXXXXXXXXXXXXXXXX
          XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...............XXXXXXXXXXXXXXXXXXXXXXXXX
          XXXXXXXXXXXXXXXXXXXXXXXXXXXX...............XXXXXXXXXXXXXXXXXXXXXXXXXXX
          XXXXXXXXXXXXXXXXXXXXXXXX.................XXXXXXXXXXXXXXXXXXXXXXXXXXXXX
          XXXXXXXXXXXXXXXXXXXX...................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
          XXXXXXXXXXXXXX......................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

```

(Can you see the indent?! ;-) )

# Answer
> 8 votes
## APL (74)

```
{L←⍴⊃C Y X⎕IO←⍞⎕⎕0⋄⎕←{C[⊃⌊L⌊35÷⍨L×.5*⍨+/2*⍨1 2÷⍨⍵-Y X]}¨⍳⍵}25 70

```

The reason it's wrapped in a function is that the modification to `⎕IO` doesn't apply to the rest of the system.

Explanation:

* `L←⍴⊃C Y X⎕IO←⍞⎕⎕0`: Set `⎕IO` to `0` (making arrays 0-based instead of 1-based), set X to  (first line read), set Y to  (second line read), set C to  (third line read, with no formatting), and set L to the length () of `C`.
* `25 70`: the dimensions of the matrix.
* `¨⍳⍵`: for each element in the matrix where each element is its own coordinates...
* `⍵-Y X`: difference between the current point and the center point
* `1 2÷⍨`: divide the X coordinate by 2 (because a char is half as wide as it is tall)
* `.5*⍨+/2*⍨`: take the square root of the sum of the squares
* `35÷⍨`: divide by 35
* `⌊L⌊`: take the minimum of the amount of characters and the current value and round it down
* `,/`: The values are still wrapped in a list (of only one element), and this will create spacing in the output, so 'free' the values from their lists.
* `C[`...`]`: use the value we found as an index into the character list
* `⎕←`: we now have a matrix where each element (x,y) is the character for (x,y), so output the matrix.

# Answer
> 6 votes
# Perl 5.10, 103 chars

```
$x=<>;$y=<>;@C=<>=~/./g;for$j(-$y..24-$y){print+(map$C[@C/35*sqrt$_**2/4+$j**2]//$C[-1],-$x..69-$x),$/}

```

# Answer
> 5 votes
## Perl, 120 chars

```
$x,$y=<>,<>;@C=split'',<>;for$j(0..24){print+(map$C[($c=$#C/35*sqrt(($x/2-$_/2)**2+($y-$j)**2))<$#C?$c:$#C-1],0..69),$/}

```

# Answer
> 4 votes
## Windows PowerShell, 157

Nothing noteworthy. Beaten to death already:

```
$x,$y,$c=@($input)
$l=$c.Length
$c+=(""+$c[-1])*90
0..24|%{$r=$_
-join(0..69|%{$c[[math]::truncate([math]::sqrt(($x-$_)*($x-$_)+4*($y-$r)*($y-$r))*$l/70)]})}

```

# Answer
> 2 votes
## C, 176

Here a translation of my Delphi solution to C, saving 24 characters :

```
X,Y,l,i,j,t;char G[99];main(){scanf("%d\n%d\n",&X,&Y);gets(G);l=strlen(G);for(j=-Y;j<25-Y;j++)for(i=-X-1;i<70-X;)t=floor(l*sqrt(i*i++/4+j*j)/35),putchar(!i+X?10:G[t<l?t:l-1]);}

```

You can test this code here : http://www.ideone.com/oTvHt

# Answer
> 2 votes
### Common Lisp, 173 characters

```
(let*((c(read))(v(read))(g(read-line))(l(length g)))(dotimes(y 25)(dotimes(x 70)(princ(elt g(min(floor(*(sqrt(+(expt(/(- c x)2)2)(expt(- v y)2)))l)35)(1- l)))))(princ #\
)))

```

The only real trick I use here is using

```
#\[actual newline]

```

as a newline character literal

# Answer
> 1 votes
### C# 311

Thought I'd make a long program to make the others feel better:

```
using System;class P{static void Main(){Func<string>r=Console.ReadLine;int x=int.Parse(r()),y=int.Parse(r());var c=r();for(int j=0;j<25;j++){for(int i=0;i<70;i++){var l=c.Length;Console.Write(c[(int)Math.Min(l*Math.Sqrt(Math.Pow(Math.Abs(x-i)/2.0,2)+Math.Pow(Math.Abs(y-j),2))/35,l-1)]);}Console.Write("\n");}}}

```

Input is taken from the console, one line at a time (two lines for the coordinates and one for the gradient chars).

Thanks to Joey for the tips.

Sample 1: http://ideone.com/X0jIZ

Sample 2: http://ideone.com/RvICt

# Answer
> 1 votes
### scala 223 (204 without App-Wrapper)

```
object C extends App{
import math._
def r=readInt
val p=r
val q=r
val m=readLine
(1 to 70)map(x=>(0 to 25)map(y=>{
printf("%c[%d;%dH%s",27,y,x,m(({
val a=abs(p-x)
val b=abs(q-y)
sqrt(a*a+2*b*b)
}*(m.size-1)/74).toInt))}
))}

```

Having cols and rows (70, 25) set dynamically would allow for screenfilling gradients.

---
Tags: code-golf, ascii-art
---


title: Find The Wordiest Combination Lock

text:
# Question
Title: Find The Wordiest Combination Lock
I have a combination padlock which has letters instead of numbers. It looks like this: http://pictures.picpedia.com/2012/09/Word\_Combination\_Padlock.jpg There are 5 reels, each of which has 10 different letters on it.

Most people like to use a word for their combination rather than an arbitrary string of letters. (Less secure, of course, but easier to remember.) So when manufacturing the lock, it would be good to build it to have a combination of letters which can be used to create as many 5-letter English words as possible.

Your task, should you choose to accept it, is to find an assignment of letters to reels which will allow as many words as possible to be created. For example, your solution might be

ABCDEFGHIJ DEFGHIJKLM ZYXWVUTSR ABCDEFGHIJ ABCDEFGHIJ

(If you weren't feeling too imaginative, that is).

For consistency, please use the word list at http://www.cs.duke.edu/~ola/ap/linuxwords

Any 5-letter word in that list is OK, including proper names. Ignore Sino- and L'vov and any other words in the list which contain a non a-z character.

The winning program is the one which produces the largest set of words. In the event that multiple programs find the same result, the first one to be posted wins. The program should run in under 5 minutes.

Edit: since activity has died down, and no better solutions have come out, I declare Peter Taylor the winner! Thanks everyone for your inventive solutions.

# Answer
> 6 votes
## 1275 words by simple greedy hill-climbing

Code is C#. Solution produced is

```
Score 1275 from ^[bcdfgmpstw][aehiloprtu][aeilnorstu][acdeklnrst][adehklrsty]$

```

I'm using that output format because it's really easy to test:

```
grep -iE "^[bcdfgmpstw][aehiloprtu][aeilnorstu][acdeklnrst][adehklrsty]$" linuxwords.txt | wc

```

---

```
namespace Sandbox {
    class Launcher {
        public static void Main(string[] args)
        {
            string[] lines = _Read5s();
            int[][] asMasks = lines.Select(line => line.ToCharArray().Select(ch => 1 << (ch - 'a')).ToArray()).ToArray();
            Console.WriteLine(string.Format("{0} words found", lines.Length));

            // Don't even bother starting with a good mapping.
            int[] combos = _AllCombinations().ToArray();
            int[] best = new int[]{0x3ff, 0x3ff, 0x3ff, 0x3ff, 0x3ff};
            int bestSc = 0;
            while (true)
            {
                Console.WriteLine(string.Format("Score {0} from {1}", bestSc, _DialsToString(best)));

                int[] prevBest = best;
                int prevBestSc = bestSc;

                // Greedy hill-climbing approach
                for (int off = 0; off < 5; off++)
                {
                    int[] dials = (int[])prevBest.Clone();

                    dials[off] = (1 << 26) - 1;
                    int[][] filtered = asMasks.Where(mask => _Permitted(dials, mask)).ToArray();
                    int sc;
                    dials[off] = _TopTen(filtered, off, out sc);
                    if (sc > bestSc)
                    {
                        best = (int[])dials.Clone();
                        bestSc = sc;
                    }
                }

                if (bestSc == prevBestSc) break;
            }

            Console.WriteLine("Done");
            Console.ReadKey();
        }

        private static int _TopTen(int[][] masks, int off, out int sc)
        {
            IDictionary<int, int> scores = new Dictionary<int, int>();
            for (int k = 0; k < 26; k++) scores[1 << k] = 0;

            foreach (int[] mask in masks) scores[mask[off]]++;

            int rv = 0;
            sc = 0;
            foreach (KeyValuePair<int, int> kvp in scores.OrderByDescending(kvp => kvp.Value).Take(10))
            {
                rv |= kvp.Key;
                sc += kvp.Value;
            }
            return rv;
        }

        private static string _DialsToString(int[] dials)
        {
            StringBuilder sb = new StringBuilder("^");
            foreach (int dial in dials)
            {
                sb.Append('[');
                for (int i = 0; i < 26; i++)
                {
                    if ((dial & (1 << i)) != 0) sb.Append((char)('a' + i));
                }
                sb.Append(']');
            }
            sb.Append('$');
            return sb.ToString();
        }

        private static IEnumerable<int> _AllCombinations()
        {
            // \binom{26}{10}
            int set = (1 << 10) - 1;
            int limit = (1 << 26);
            while (set < limit)
            {
                yield return set;

                // Gosper's hack:
                int c = set & -set;
                int r = set + c;
                set = (((r ^ set) >> 2) / c) | r;
            }
        }

        private static bool _Permitted(int[] dials, int[] mask)
        {
            for (int i = 0; i < dials.Length; i++)
            {
                if ((dials[i] & mask[i]) == 0) return false;
            }
            return true;
        }

        private static string[] _Read5s()
        {
            System.Text.RegularExpressions.Regex word5 = new System.Text.RegularExpressions.Regex("^[a-z][a-z][a-z][a-z][a-z]$", System.Text.RegularExpressions.RegexOptions.Compiled);
            return File.ReadAllLines(@"d:\tmp\linuxwords.txt").Select(line => line.ToLowerInvariant()).Where(line => word5.IsMatch(line)).ToArray();
        }
    }
}

```

# Answer
> 4 votes
# Python (3), 1273 ≈ 30.5%

This is a really naïve approach: keep a tally of the frequency of each letter in each position, then eliminate the "worst" letter until the remaining letters will fit on the reels. I'm surprised it seems to do so well.

What's most interesting is that I have almost exactly the same output as the C# 1275 solution, except I have an `N` on my last reel instead of `A`. That `A` was my 11th-to-last elimination, too, even before throwing away a `V` and a `G`.

```
from collections import Counter

def main(fn, num_reels, letters_per_reel):
    # Read ye words
    words = []
    with open(fn) as f:
        for line in f:
            word = line.strip().upper()
            if len(word) == num_reels and word.isalpha():
                words.append(word)

    word_pool_size = len(words)

    # Populate a structure of freq[reel_number][letter] -> count
    freq = [Counter() for _ in range(num_reels)]
    for word in words:
        for r, letter in enumerate(word):
            freq[r][letter] += 1

    while True:
        worst_reelidx = None
        worst_letter = None
        worst_count = len(words)
        for r, reel in enumerate(freq):
            # Skip reels that already have too-few letters left
            if len(reel) <= letters_per_reel:
                continue

            for letter, count in reel.items():
                if count < worst_count:
                    worst_reelidx = r
                    worst_letter = letter
                    worst_count = count

        if worst_letter is None:
            # All the reels are done
            break

        # Discard any words containing this worst letter, and update counters
        # accordingly
        filtered_words = []
        for word in words:
            if word[worst_reelidx] == worst_letter:
                for r, letter in enumerate(word):
                    freq[r][letter] -= 1
                    if freq[r][letter] == 0:
                        del freq[r][letter]
            else:
                filtered_words.append(word)
        words = filtered_words

    for reel in freq:
        print(''.join(sorted(reel)))

    print("{} words found (~{:.1f}%)".format(
        len(words), len(words) / word_pool_size * 100))

```

Produces:

```
BCDFGMPSTW
AEHILOPRTU
AEILNORSTU
ACDEKLNRST
DEHKLNRSTY
1273 words found (~30.5%)

```

# Answer
> 3 votes
## *Mathematica*, 1275 words again and again...

This code is not Golfed as the question does not appear to call for that.

```
wordlist = Flatten @ Import @ "http://www.cs.duke.edu/~ola/ap/linuxwords";
shortlist = Select[ToLowerCase@wordlist, StringMatchQ[#, Repeated[LetterCharacter, {5}]] &];
string = "" <> Riffle[shortlist, ","];

set = "a" ~CharacterRange~ "z";
gb = RandomChoice[set, {5, 10}];

best = 0;
While[True,
  pos = Sequence @@ RandomInteger /@ {{1, 5}, {1, 10}};
  old = gb[[pos]];
  gb[[pos]] = RandomChoice @ set;
  If[best < #,
    best = #; Print[#, "   ", StringJoin /@ gb],
    gb[[pos]] = old
  ] & @ StringCount[string, StringExpression @@ Alternatives @@@ gb]
]

```

The word count quickly (less than 10 seconds) evolves to 1275 on most runs but never gets beyond that. I tried perturbing the letters by more than one at a time in an attempt to get out of a theoretical local maximum but it never helped. I strongly suspect that 1275 is the limit for the given word list. Here is a complete run:

> ```
> 36   {tphcehmqkt,agvkqxtnpy,nkehuaakri,nsibxpctio,iafwdyhone}
>
> 37   {tpicehmqkt,agvkqxtnpy,nkehuaakri,nsibxpctio,iafwdyhone}
>
> 40   {tpicehmqkt,agvkqxtnpy,nkehuaakri,nsibxpctio,iafldyhone}
>
> 42   {tpicehmqkt,agvkqxtnpy,nkehuaakri,nsfbxpctio,iafldyhone}
>
> 45   {tpicehmrkt,agvkqxtnpy,nkehuaakri,nsfbxpctio,iafldyhone}
>
> 48   {tpicehmrkt,agvkwxtnpy,nkehuaakri,nsfbxpctio,iafldyhone}
>
> 79   {tpicehmskt,agvkwxtnpy,nkehuaakri,nsfbxpctio,iafldyhone}
>
> 86   {tpicehmskt,agvkwxtnpy,nkehuaakri,esfbxpctio,iafldyhone}
>
> 96   {tpicehmskt,agvkwxtnpy,nkehuaokri,esfbxpctio,iafldyhone}
>
> 97   {tpicehmskt,agvkwxtnpy,nkehuaokri,esfbxpctio,ipfldyhone}
>
> 98   {tpicehmskv,agvkwxtnpy,nkehuaokri,esfbxpctio,ipfldyhone}
>
> 99   {tpicehmskv,agvkwxtnpy,nkehuaokri,esfbzpctio,ipfldyhone}
>
> 101   {tpicehmskv,agvkwxtnpy,nkehuaokri,esfhzpctio,ipfldyhone}
>
> 102   {tpicehmskv,agvkwxtnpy,nkehuaokri,esfhzpctno,ipfldyhone}
>
> 105   {tpicehmskv,agvkwxtnpy,nkehuaokri,esfhzmctno,ipfldyhone}
>
> 107   {tpicehmskn,agvkwxtnpy,nkehuaokri,esfhzmctno,ipfldyhone}
>
> 109   {tpgcehmskn,agvkwxtnpy,nkehuaokri,esfhzmctno,ipfldyhone}
>
> 115   {tpgcehmsan,agvkwxtnpy,nkehuaokri,esfhzmctno,ipfldyhone}
>
> 130   {tpgcehmsan,agvkwxtnpy,nkehuaokri,esfhzmctno,ipfldyhons}
>
> 138   {tpgcehmsan,agvkwxtnpy,nkehuaokri,esfhzmctno,ipfldytons}
>
> 143   {tpgcehmsab,agvkwxtnpy,nkehuaokri,esfhzmctno,ipfldytons}
>
> 163   {tpgcehmsab,auvkwxtnpy,nkehuaokri,esfhzmctno,ipfldytons}
>
> 169   {tpgcehmsab,auvkwctnpy,nkehuaokri,esfhzmctno,ipfldytons}
>
> 176   {tpgcehmsab,auvkwctnpy,nkehuaokri,esfhzmctno,ihfldytons}
>
> 189   {tpgcehmsab,auvkwchnpy,nkehuaokri,esfhzmctno,ihfldytons}
>
> 216   {tpgcehmsab,auvkwchnpy,nkehtaokri,esfhzmctno,ihfldytons}
>
> 220   {tpgcehmsab,auvkwthnpy,nkehtaokri,esfhzmctno,ihfldytons}
>
> 223   {tpgcehmsab,auvkwthnpy,nkehtaokri,esfhbmctno,ihfldytons}
>
> 234   {tpgcehmsab,auvkwthnpy,nkegtaokri,esfhbmctno,ihfldytons}
>
> 283   {tpgcehmsab,auvkwthnpy,nkegtaokri,esfhbrctno,ihfldytons}
>
> 285   {tpdcehmsab,auvkwthnpy,nkegtaokri,esfhbrctno,ihfldytons}
>
> 313   {tpdcehmsab,auvkwthnly,nkegtaokri,esfhbrctno,ihfldytons}
>
> 371   {tpdcehmsab,auvkethnly,nkegtaokri,esfhbrctno,ihfldytons}
>
> 446   {tpdcehmsab,auvoethnly,nkegtaokri,esfhbrctno,ihfldytons}
>
> 451   {tpdcehmslb,auvoethnly,nkegtaokri,esfhbrctno,ihfldytons}
>
> 465   {tpdcwhmslb,auvoethnly,nkegtaokri,esfhbrctno,ihfldytons}
>
> 545   {tpdcwhmslb,auioethnly,nkegtaokri,esfhbrctno,ihfldytons}
>
> 565   {tpdcwhmslb,auioethnly,nkegtaocri,esfhbrctno,ihfldytons}
>
> 571   {tpdcwhmslb,auioethnly,nkegtaocri,esfhwrctno,ihfldytons}
>
> 654   {tpdcwhmslb,auioethnly,nkegtaocri,esfhwrctno,ihfedytons}
>
> 671   {tpdcwhmslb,auioethnly,nkegtaocri,esfhirctno,ihfedytons}
>
> 731   {tpdcwhmslb,auioethnly,nkegtaocri,esfhirctno,ihredytons}
>
> 746   {tpdcwhmslb,arioethnly,nkegtaocri,esfhirctno,ihredytons}
>
> 755   {tpdcwhmslb,arioethnuy,nkegtaocri,esfhirctno,ihredytons}
>
> 772   {tpdcwhmslb,arioethnuy,nkegtaocri,ekfhirctno,ihredytons}
>
> 786   {tpdcwhmslb,arioethnuy,nkegtaocri,ekfhirctno,lhredytons}
>
> 796   {tpdcwhmslb,arioethnuy,nkegtaocri,ekfhgrctno,lhredytons}
>
> 804   {tpdcwhmslb,arioethwuy,nkegtaocri,ekfhgrctno,lhredytons}
>
> 817   {tpdcwhmslb,arioethwuy,nklgtaocri,ekfhgrctno,lhredytons}
>
> 834   {tpdcwhmslb,arioethwuy,nklgtaocri,ekfhdrctno,lhredytons}
>
> 844   {tpdcwhmslb,arioethwup,nklgtaocri,ekfhdrctno,lhredytons}
>
> 887   {tpdcwhmslb,arioethwup,nklgtaocri,ekshdrctno,lhredytons}
>
> 901   {tpdcwhmslb,arioethwup,nklgtaouri,ekshdrctno,lhredytons}
>
> 966   {tpdcwhmslb,arioethwup,nklgtaouri,elshdrctno,lhredytons}
>
> 986   {tpdcwhmsfb,arioethwup,nklgtaouri,elshdrctno,lhredytons}
>
> 1015   {tpdcwhmsfb,arioethwup,nklgtaouri,elsidrctno,lhredytons}
>
> 1039   {tpdcwhmsfb,arioethwup,nklgtaouri,elsidrctno,khredytons}
>
> 1051   {tpdcwhmsfb,arioethwup,nklgtaouri,elskdrctno,khredytons}
>
> 1055   {tpdcwhmsfb,arioethwup,nklgtaouri,elskdrctno,khredytlns}
>
> 1115   {tpdcwhmsfb,arioethwup,nelgtaouri,elskdrctno,khredytlns}
>
> 1131   {tpdcwhmsfb,arioethwup,nelwtaouri,elskdrctno,khredytlns}
>
> 1149   {tpdcwhmsfb,arioethwup,nelwtaouri,elskdrctna,khredytlns}
>
> 1212   {tpdcwhmsfb,arioelhwup,nelwtaouri,elskdrctna,khredytlns}
>
> 1249   {tpdcwhmsfb,arioelhwup,nelstaouri,elskdrctna,khredytlns}
>
> 1251   {tpgcwhmsfb,arioelhwup,nelstaouri,elskdrctna,khredytlns}
>
> 1255   {tpgcwdmsfb,arioelhwup,nelstaouri,elskdrctna,khredytlns}
>
> 1258   {tpgcwdmsfb,arioelhwup,nelstaouri,elskdrctna,khredytlas}
>
> 1262   {tpgcwdmsfb,arioelhwut,nelstaouri,elskdrctna,khredytlas}
>
> 1275   {tpgcwdmsfb,arioelhput,nelstaouri,elskdrctna,khredytlas}
>
> ```

Here are some other "winning" selections:

```
{"cbpmsftgwd", "hriuoepatl", "euosrtanli", "clknsaredt", "yhlkdstare"}
{"wptdsgcbmf", "ohlutraeip", "erotauinls", "lknectdasr", "sytrhklaed"}
{"cftsbwgmpd", "ropilhtaue", "niauseltor", "clstnkdrea", "esdrakthly"}
{"smgbwtdcfp", "ihulpreota", "ianrsouetl", "ekndasctlr", "kehardytls"}

```

As Peter comments these are actually the same solution in different orders. Sorted:

```
{"bcdfgmpstw", "aehiloprtu", "aeilnorstu", "acdeklnrst", "adehklrsty"}

```

# Answer
> 2 votes
## Python, 1210 words (~ 29%)

Assuming I counted the words correctly this time, this is slightly better than FakeRainBrigand's solution. The only difference is I add each reel in order, and then remove all words from the list that don't match the reel so I get a slightly better distribution for the next reels. Because of this, it gives the exact same first reel.

```
word_list = [line.upper()[:-1] for line in open('linuxwords.txt','r').readlines() if len(line) == 6]
cur_list = word_list
s = ['']*5
for i in range(5):
    count = [0]*26
    for j in range(26):
        c = chr(j+ord('A'))
        count[j] = len([x for x in cur_list if x[i] == c])
    s[i] = [chr(x+ord('A')) for x in sorted(range(26),lambda a,b: count[b] - count[a])[:10]]
    cur_list = filter(lambda x:x[i] in s[i],cur_list)
for e in s:
    print ''.join(e)
print len(cur_list)

```

The program outputs

```
SBCAPFDTMG
AOREILUHTP
ARIOLENUTS
ENTLRCSAID
SEYDTKHRNL
1210

```

# Answer
> 1 votes
# iPython (273 210 Bytes, 1115 words)

### 1115/4176* ~ 27%

I calculated these in iPython, but my history (trimmed to remove debugging) looked like this.

```
with open("linuxwords") as fin: d = fin.readlines()
x = [w.lower().strip() for w in d if len(w) == 6]
# Saving for later use:
# with open("5letter", "w") as fout: fout.write("\n".join(x))
from string import lowercase as low
low=lowercase + "'"
c = [{a:0 for a in low} for q in range(5)]
for w in x:
    for i, ch in enumerate(w):
        c[i][ch] += 1

[''.join(sorted(q, key=q.get, reverse=True)[:10]) for q in c]

```

If we're going for short; I could trim it to this.

```
x = [w.lower().strip() for w in open("l") if len(w)==6]
c=[{a:0 for a in"abcdefghijklmnopqrstuvwxyz'-"}for q in range(5)]
for w in[w.lower().strip()for w in open("l") if len(w)==6]:
 for i in range(5):c[i][w[i]]+=1
[''.join(sorted(q,key=q.get,reverse=True)[:10])for q in c]

```

Shortened:

```
c=[{a:0 for a in"abcdefghijklmnopqrstuvwxyz'-"}for q in range(5)]
for w in[w.lower() for w in open("l")if len(w)==6]:
 for i in range(5):c[i][w[i]]+=1
[''.join(sorted(q,key=q.get,reverse=True)[:10])for q in c]

```

My results were: `['sbcapfdtmg', 'aoeirulhnt', 'aironeluts', 'etnlriaosc', 'seyrdtnlah']`.

\*My math on the 4176 may be a little short due to words with hyphens or apostrophes being omitted

# Answer
> 1 votes
# Q

**? (todo) words**

Words should be stored in a file called `words`

```
(!:')10#/:(desc')(#:'')(=:')(+:)w@(&:)(5=(#:')w)&(&/')(w:(_:)(0:)`:words)in\:.Q.a

```

Runs in about 170 ms on my i7. It analyses the wordlist, looking for the most common letter in each position (obviously filtering out any non-candidates). It's a lazy naive solution but produces a reasonably good result with minimal code.

Results:

```
"sbcapfdtmg"
"aoeirulhnt"
"aironeluts"
"etnlriaosc"
"seyrdtnlah"

```

# Answer
> 0 votes
**Edit:** Now that the rules have been modified, this approach is disqualified. I'm going to leave it here in case anyone is interested until I eventually getting around to modifying it for the new rules.

# Python: 277 Characters

I'm pretty sure that the generalized version of this problem is NP-Hard, and the question didn't require finding the *fastest* solution, so here's a brute-force method of doing it:

```
import itertools,string
w=[w.lower()[:-1] for w in open('w') if len(w)==6]
v=-1
for l in itertools.product(itertools.combinations(string.ascii_lowercase,10),repeat=5):
 c=sum(map(lambda d:sum(map(lambda i:i[0] in i[1],zip(d,l)))==5,w))
 if c>v:
  v=c
  print str(c)+" "+str(l)

```

Note that I renamed the word list file to just "w" to save a few characters.

The output is the number of words that are possible from a given configuration followed by the configuration itself:

```
34 (('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'))
38 (('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k'))
42 (('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'l'))
45 (('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'n'))
50 (('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'r'))
57 (('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 's'))
60 (('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'k', 's'))
64 (('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'l', 's'))
67 (('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'n', 's'))
72 (('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'), ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'r', 's'))
...

```

The last line of output before the program terminates is guaranteed to be the optimal solution.

---
Tags: code-challenge, natural-language, restricted-time
---


title: Keep track of a Roulette game

text:
# Question
Title: Keep track of a Roulette game
You're writing a program for a new automated roulette croupier to be installed in a major casino. Unfortunately, the last guy bailed out on the company and published buggy software. You're stuck with a thousand burned flash chips with only a few kilobytes of space to store a working program. Can you do it?

The task is to write a program which will accurately handle bets, wins and losses of a roulette game.

It will be run as a session. When it initialises, players place their bets which are sent through STDIN. Once all bets have been received, the input for where the ball landed is given. The program must then calculate the winnings for each of the players and the casino.

A single zero wheel is assumed. Assume dollars will be bet (not chips) and that the input is always valid. You only need to support the "outside bets" and numbered bets (lists of numbers, not named.) Payouts are described on the Wikipedia article.

Outside bet names: c1, c2, c3 (1st-3rd column), d1, d2, d3 (1st-3rd dozen), o (odd), e (even), r (red), b (black), 1-18, 19-36.

Example session (`>` indicates input, `<` indicates output):

```
> 7 800

```

Place a bet on the number "7" only, for $800.

```
> 8,9,10,11 50

```

Place a bet on the range "8,9,10,11", for $50.

```
> c1 2000

```

Place a bet on "1st column" (1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34) for $2000.

```
> ok
> 7

```

All players done. Pocketed in 7.

```
< 1 28800
< 2 0
< 3 6000

```

Payout details: #1 gets 36x original bet (35-to-1), #2 did not win and #3 gets 3x original bet (2-to-1)

```
< c -34750

```

Casino is down $34,750.

**Deciding the winner**

* Code space is critical so the smaller the program the better. The smallest program implementing all of the described features will be the winner, unless bonus features are present, in which case the best overall program will be decided based on the combination of size and features supported.
* The program must implement at least the bets described above, but support for other types, as well as number bets such as splits and baskets will be considered and may add bonus points.

# Answer
> 2 votes
## Python, 443 440 chars

```
R=range
N=37
V=91447186090
M={'e':R(0,N,2),'o':R(1,N,2),'r':[i for i in R(N)if V>>i&1],'b':[i for i in R(1,N)if~V>>i&1],'1-18':R(1,19),'19-36':R(19,N)}
for i in R(1,4):M['c%d'%i]=R(i,N,3);M['d%d'%i]=R(i*12-11,i*12+1)
for i in R(1,N):M[`i`]=[i]
B=[]
r=raw_input()
while'ok'!=r:x,k=r.split();B+=[(sum((M[y]for y in x.split(',')),[]),int(k))];r=raw_input()
z=input()
c=0
i=1
for b,k in B:v=36/len(b)*k*(z in b);print i,v;c+=k-v;i+=1
print'c',c

```

Makes `M`, a map from bet names to a list of numbers that win that bet. Then it reads the bets in, storing each one as a pair (list of numbers, dollar amount) in the list `B`. Finally, reads in the spin `z` and computes the payouts.

# Answer
> 1 votes
## Python (548)

Wow, the biggest thing I've done in a while.

```
r=[];R=range
for i in[1,12,19,30]:r+=R(i,i+7+i%2*2,2)
a=[];b='01';c=''
while'ok'!=c:
 if'c'in c:c=R(int(c[1]),37,3)
 if'd'in c:c=R(1+(int(c[1])-1)*12,13+(int(c[1])-1)*12)
 if'r'in c:c=r
 if'b'in c:c=filter(lambda x:x not in r,R(1,36))
 if'o'in c:c=R(1,36,2)
 if'e'in c:c=R(2,36,2)
 if'-'in c:e=18*(c[1]>'-');b[0]=R(1+e,19+e)
 if"'"in`c`:c=map(int,b[0].split(','))
 a+=[[c,b[1]]];b=raw_input().split();c=b[0]
a=a[1:]
i=input()
z=[(i in p[0])*int(p[1])*(36/len(p[0])+1)-int(p[1])for p in a]
for j,k in enumerate(z):print j+1,max(k,0)
print"c",-sum(z)

```

Things that can probably be compressed:

* generating the numbers for things like `e`, `o`, `d2`
* the math formula for calculating `z`

---
Tags: code-golf
---


title: Race to a Million

text:
# Question
Title: Race to a Million
This falls under the Code puzzles the best. Fastest way to render the numbers 1-million in a web browser. Preferably using PHP, but use what you must. Numbers must be more than one on a line in the web browser and must line wrap (the horizontal scroll bar must not be triggered).

rules:

1. use any loop construct that you want
2. No horizontal scrolling allowed
3. Count 1 - 1,000,000 (commas not needed, overshoot is OK)
4. Must be a language that displays results in a browser.

For my timer, I'm using:

```
$mtime = microtime();
$mtime = explode(" ",$mtime);
$mtime = $mtime[1] + $mtime[0];
$starttime = $mtime;

```

before the code and

```
$mtime = microtime();
$mtime = explode(" ",$mtime);
$mtime = $mtime[1] + $mtime[0];
$endtime = $mtime;
$totaltime = ($endtime - $starttime);

echo ("<br /><br /><b>Total count time:</b> ".$totaltime." seconds");

```

after the code.

# Answer
> 7 votes
# HTML

Just have a page with the numbers already in it! Encoded in base-36 for less characters and rendering time. 5 and a bit MB source so I'll just give you a little snippet:

```
<html><div style="width:100%; word-wrap:break-word;">1 2 3 4 5 6 7 8 9 a b c...

... pew2 pew3 pew4 pew5 pew6 pew7 pew8 pew9 pewa pewb pewc pewd pewe pewf pewg pewh pewi
 pewj pewk pewl pewm pewn pewo pewp pewq pewr pews pewt pewu pewv peww pewx pex0 pex1 pex2
 pex3 pex4 pex5 pex6 pex7 pex8 pex9 pexa pexb pexc pexd pexe pexf pexg pexh pexi pexj pexk
 pexl pexm pexn pexo pexp pexq pexr pexs pext pexu pexv pexw pexx pf00 pf01 pf02 pf03 pf04
 pf05 pf06 pf07 pf08 pf09 pf0a pf0b pf0c pf0d pf0e pf0f pf0g pf0h pf0i pf0j pf0k pf0l pf0m
 pf0n pf0o pf0p pf0q pf0r pf0s pf0t pf0u pf0v pf0w pf0x pf10 pf11 pf12 pf13 pf14 pf15 pf16
 pf17 pf18 pf19 pf1a pf1b pf1c pf1d pf1e pf1f pf1g pf1h pf1i pf1j pf1k pf1l pf1m pf1n pf1o
 pf1p pf1q </div></html>

```

If you can be bothered, write this to an image with really small fontsize and it may increase rendering time!

Up to OP to figure out how to time this.

(This is barely a serious submission)

# Answer
> 5 votes
# PNG, 7874 bytes

This renders almost instantaneously in Firefox. There are 512 numbers on each line. Each number is displayed in base 16,777,216 as a single RGB pixel, with the numerical value of each being `65536 * R + 256 * G + B`. The horizontal scroll bar will not be triggered in Firefox when you view an image.

The image was created in Mathematica using

```
Image[
  Partition[
    Table[IntegerDigits[x, 256, 3], {x, 1, 1000000}],
    512, 512, {1, 1}, {{255, 255, 255}}],
  "Byte", Magnification -> 1]

```

, exported as a PNG, and optimized.

# Answer
> 2 votes
## HTML / Javascript

A semi-serious attempt. This is, in my opinion, one of the only sane ways to go about the problem. Render time is approximately 1-2 seconds for every browser I checked.

```
<html>
  <head>
    <title>Count</title>
    <script type="text/javascript">
      function load_me() {
        var output_area = document.getElementById('output_area');
        var str = '';
        for(var i=1; i <= 1000000; i++) {
          str += i + ' ';
        }
        output_area.innerText = str;
      }
    </script>
    <style type="text/css">
    #output_area {
      height: 100%;
      width: 100%;
    }
    </style>
  </head>
  <body onload="load_me()">
    <textarea id="output_area"></textarea>
  </body>
</html>

```

# Answer
> 1 votes
Using ruby and the web-framework sinatra:

```
# file: million.rb
require 'sinatra';get '/million.txt' do (1..(10*100*1000)).to_a.join("\n") end

```

Usage (requires ruby installed):

```
gem install sinatra
ruby million.rb

```

Then open `http://0.0.0.0:4567/million.txt` in any browser - took 636 ms hosted locally, opened in google-chrome.

Have fun ;)

---
Tags: fastest-code
---


title: Build a Killer Sudoku Solver

text:
# Question
Title: Build a Killer Sudoku Solver
You thought regular sudoku was hard, now try Killer Sudoku!

In the game of Killer Sudoku, you aren't given any numbers at all. Instead, you're given regions that are said to add up to a certain number. Consider the following example, from Wikipedia:

And its solution:

The program you write will take a format consisting of a sequence of 81 letters representing regions, followed by a sequence of numbers. Then each number in the sequence represents the sum of the numbers in each of the letter regions, starting from "A", "B", etc.

It will then output a sequence of 81 digits representing the solution.

For example, the example puzzle above would have the following input:

```
AABBBCDEFGGHHCCDEFGGIICJKKFLMMINJKOFLPPQNJOORSPTQNUVVRSTTQWUUXXSYZWWaaXXSYZWbbbcc
3 15 22 4 16 15 25 17 9 8 20 6 14 17 17 13 20 12 27 6 20 6 10 14 8 16 15 13 17

```

And the resulting output would be:

```
215647398368952174794381652586274931142593867973816425821739546659428713437165289

```

You may assume that the input is valid, and that the regions will always appear in order by A, B, ..., Y, Z, a, b, ..., z.

(Shortest code that works wins.)

# Answer
> 4 votes
## R - 378 characters

Assuming

```
x="AABBBCDEFGGHHCCDEFGGIICJKKFLMMINJKOFLPPQNJOORSPTQNUVVRSTTQWUUXXSYZWWaaXXSYZWbbbcc"
y="3 15 22 4 16 15 25 17 9 8 20 6 14 17 17 13 20 12 27 6 20 6 10 14 8 16 15 13 17"

```

378 characters:

```
z=strsplit
v=sapply
R=rep(1:9,9)
C=rep(1:9,e=9)
N=1+(R-1)%/%3+3*(C-1)%/%3
G=z(x,"")[[1]]
M=as.integer(z(y," ")[[1]])[order(unique(G))]
s=c(1,rep(NA,80))
i=1
repeat if({n=function(g)!any(v(split(s,g),function(x)any(duplicated(x,i=NA))))
S=v(split(s,G),sum)
n(R)&&n(C)&&n(N)&&n(G)&&all(is.na(S)|S==M)}){if(i==81)break;i=i+1;s[i]=1}else{while(s[i]==9){s[i]=NA
i=i-1};s[i]=s[i]+1}
s

```

takes about an hour on my modest PC to reach the expected solution, after 2,964,690 iterations.

---

De-golfed:

```
ROWS   <- rep(1:9, 9)
COLS   <- rep(1:9, each = 9)
NONETS <- 1 + (ROWS - 1) %/% 3 + 3 * (COLS - 1) %/% 3
CAGES  <- strsplit(x, "")[[1]]
SUMS   <- as.integer(strsplit(y, " ")[[1]])[order(unique(CAGES))]

is.valid <- function(sol) {

   has.no.repeats <- function(sol, grouping) {
      !any(vapply(split(sol, grouping),
                  function(x) any(duplicated(x, incomparables = NA)),
                  logical(1)))
   }
   has.exp.sum <- function(sol, grouping, exp.sums) {
      sums <- vapply(split(sol, grouping), sum, integer(1))
      all(is.na(sums) | sums == exp.sums)
   }

   has.no.repeats(sol, ROWS  ) &&
   has.no.repeats(sol, COLS  ) &&
   has.no.repeats(sol, NONETS) &&
   has.no.repeats(sol, CAGES ) &&
   has.exp.sum(sol, CAGES, SUMS)
}

sol <- c(1L, rep(NA, 80)) # start by putting a 1
i <- 1L                   # in the first cell
it <- 0L

repeat {
   it <- it + 1L
   if (it %% 100L == 0L) print(sol)
   if(is.valid(sol)) {         # if everything looks good
      if (i == 81L) break         # we are either done
      i <- i + 1L                 # or we move to the next cell
      sol[i] <- 1L                # and make it a 1
   } else {                    # otherwise
      while (sol[i] == 9L) {      # while 9s are found
         sol[i] <- NA             # replace them with NA
         i <- i - 1L              # and move back to the previous cell
      }
      sol[i] <- sol[i] + 1L       # when a non-9 is found, increase it
   }                           # repeat
}
sol

```

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

```
n%~[~]:N;1/:P.&:L;9..*?{(.[{.9%)\9/}81*;]:§;L{.`{\~@@=*}+[P§]zip%{+}*\L?N==}%§9/..zip+\3/{{3/}%zip{{+}*}%}%{+}*+{.&,9=}%+1-,!{§puts}*.}do;

```

This is a killer sudoku solver in GolfScript. It expects input on STDIN in two rows as given in the example above.

Please note: Since the puzzle description does not make any restrictions on execution time I preferred small code size over speed. The code tests all 9^81 grid configurations for a solution which may take some time on a slow computer ;-)

# Answer
> 4 votes
### Ruby, 970 characters

```
A,B=gets,gets.split
L=[]
R=[]
U=[]
D=[]
N=[]
C=[]
S=[]
O=[0]*81
z='A'
(0..324).map{|j|U<<j;D<<j;R<<(j+1)%325;L<<(j+324)%325;N<<j;C<<j;S<<0}
X=->s,j,c,cf,n{j<81?(z==A[j]?(0..8).map{|i|X[s-1-i,j+1,c+[i],cf+[1+j,1+81+27*i+j/9,1+81+27*i+9+j%9,1+81+27*i+18+j/3%3+j/27*3],n+[i+1]]}:X[s,j+1,c,cf,n+[0]]if s>=0):(h=U.size;cf.uniq.sort.map{|l|N<<n;L<<(L[h]||h);R<<h;U<<U[l];D<<l;C<<l;S[l]+=1;L[R[-1]]=R[L[-1]]=U[D[-1]]=D[U[-1]]=L.size-1}if s==0)}
Y=->c{L[R[c]]=L[c];R[L[c]]=R[c];i=D[c];(j=R[i];(U[D[j]]=U[j];D[U[j]]=D[j];S[C[j]]-=1;j=R[j])while j!=i;i=D[i])while i!=c}
Z=->c{i=U[c];(j=L[i];(S[C[j]]+=1;U[D[j]]=j;D[U[j]]=j;j=L[j])while j!=i;i=U[i])while i!=c;L[R[c]]=c;R[L[c]]=c}
B.map{|k|X[k.to_i,0,[],[],[]];z=z=='Z'?'a':z.next}
s=->k{c=R[0];c<1?($><<(O[0,k].map{|s|N[s]}.transpose.map &:max)*""):(g=S[b=c];g=S[b=c]if S[c]<g while 0<c=R[c];Y[b];r=D[b];(O[k]=r;j=R[r];(Y[C[j]];j=R[j])while j!=r;s[k+1];r=O[k];c=C[r];j=L[r];(Z[C[j]];j=L[j])while j!=r;r=D[r])while r!=b;Z[b])}
s[0]

```

The above ruby code is opposite to my GolfScript subscription. It is quite long (and not yet fully golfed), but optimized for speed. The killer sudoku given above is solved in well under a second (with my original java version it was only a few milli seconds). The solver itself is a basic implementation of Knuth's DLX algorithm.

Input must be given as two lines on STDIN. Example (online):

```
> AABBBCDEFGGHHCCDEFGGIICJKKFLMMINJKOFLPPQNJOORSPTQNUVVRSTTQWUUXXSYZWWaaXXSYZWbbbcc
3 15 22 4 16 15 25 17 9 8 20 6 14 17 17 13 20 12 27 6 20 6 10 14 8 16 15 13 17

215647398368952174794381652586274931142593867973816425821739546659428713437165289

```

---
Tags: code-golf, sudoku, puzzle-solver
---


# Question
Title: Longest non-repeating Game-of-Life sequence
Given a positive integer N, determine the starting pattern on a N x N-grid that yield the longest non-repeating sequence under Game of Life-rules, and ends with a fixed pattern (cycle of length 1), played on a torus.

The goal is not the shortest program, but the quickest.

Since the world is finite, you will eventually end up in a loop, thus repeating an already visited state. If this loop has period 1, then the starting pattern is a valid candidate.

Output: Starting pattern and total number of unique states in the sequence (including starting pattern).

Now, the 1x1-torus is special, since a cell may be considered neighbouring to itself or not, but in practice, there is no problem, a single living cell will in either case just die (of overcrowding or loneliness). Thus, input 1 yields a sequence of length 2, the sequence being one cell living, then forever dead.

The motivation for this question is that is an analogue of the busy beaver function, but definitely less complex, since we have a bound on memory. This will be a nice sequence to include on OEIS, as well.

For N=3, the sequence length is 3, any pattern on the left hand side reaches a completely black 3x3-square, and then dies. (All patterns that are part of 1-cycle removed).

# Answer
> 13 votes
## C++ up to N=6

```
3x3 answer 3: 111 000 000
4x4 answer 10: 1110 0010 1100 0000
5x5 answer 52: 11010 10000 11011 10100 00000
6x6 answer 91: 100011 010100 110011 110100 101000 100000

```

This technique is centered around a fast next state function. Each board is represented as a bitmask of N^2 bits, and bit-twiddly tricks are used to compute the next state for all cells at once. `next` compiles down to about 200 100 assembly instructions for N \<= 8. Then we just do the standard try-all-states-until-they-repeat and pick the longest one.

Takes a few seconds up to 5x5, a few hours for 6x6.

```
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

#define N 6

typedef uint64_t board;

// board is N bits by N bits, with indexes like this (N=4):
//  0  1  2  3
//  4  5  6  7
//  8  9 10 11
// 12 13 14 15

#if N==3
#define LEFT_COL (1 + (1<<3) + (1<<6))
#define RIGHT_COL ((1<<2) + (1<<5) + (1<<8))
#define ALL 0x1ffULL
#elif N==4
#define LEFT_COL 0x1111ULL
#define RIGHT_COL 0x8888ULL
#define ALL 0xffffULL
#elif N==5
#define LEFT_COL (1ULL + (1<<5) + (1<<10) + (1<<15) + (1<<20))
#define RIGHT_COL ((1ULL<<4) + (1<<9) + (1<<14) + (1<<19) + (1<<24))
#define ALL 0x1ffffffULL
#elif N==6
#define LEFT_COL (1 + (1<<6) + (1<<12) + (1<<18) + (1<<24) + (1ULL<<30))
#define RIGHT_COL ((1<<5) + (1<<11) + (1<<17) + (1<<23) + (1<<29) + (1ULL<<35))
#define ALL 0xfffffffffULL
#else
#error "bad N"
#endif

static inline board north(board b) {
  return (b >> N) + (b << N*N-N);
}
static inline board south(board b) {
  return (b << N) + (b >> N*N-N);
}
static inline board west(board b) {
  return ((b & ~LEFT_COL) >> 1) + ((b & LEFT_COL) << N-1);
}
static inline board east(board b) {
  return ((b & ~RIGHT_COL) << 1) + ((b & RIGHT_COL) >> N-1);
}

board next(board b) {
  board n1 = north(b);
  board n2 = south(b);
  board n3 = west(b);
  board n4 = east(b);
  board n5 = north(n3);
  board n6 = north(n4);
  board n7 = south(n3);
  board n8 = south(n4);

  // add all the bits bitparallel-y to a 2-bit accumulator with overflow
  board a0 = 0;
  board a1 = 0;
  board overflow = 0;
#define ADD(x) overflow |= a0 & a1 & x; a1 ^= a0 & x; a0 ^= x;

  a0 = n1; // no carry yet
  a1 ^= a0 & n2; a0 ^= n2; // no overflow yet
  a1 ^= a0 & n3; a0 ^= n3; // no overflow yet
  ADD(n4);
  ADD(n5);
  ADD(n6);
  ADD(n7);
  ADD(n8);
  return (a1 & (b | a0)) & ~overflow & ALL;
}
void print(board b) {
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      printf("%d", (int)(b >> i*N+j & 1));
    }
    printf(" ");
  }
  if (b >> N*N) printf("*");
  printf("\n");
}

int main(int argc, char *argv[]) {
  // Somewhere in the starting pattern there are a 1 and 0 together.  Using translational
  // and rotational symmetry, we can put these in the first two bits.  So we need only consider
  // 1 mod 4 boards.

  board steps[10000];
  int maxsteps = -1;
  for (board b = 1; b < 1ULL << N*N; b += 4) {
    int nsteps = 0;
    board x = b;
    while (true) {
      int repeat = steps + nsteps - find(steps, steps + nsteps, x);
      if (repeat > 0) {
        if (repeat == 1 && nsteps > maxsteps) {
          printf("%d: ", nsteps);
          print(b);
          maxsteps = nsteps;
        }
        break;
      }
      steps[nsteps++] = x;
      x = next(x);
    }
  }
}

```

# Answer
> 9 votes
I see the following possible solution approaches:

* Heavy theory. I know there is some literature on Life on a torus, but I haven't read much of it.
* Brute force forwards: for every possible board, check its score. This is basically what Matthew and Keith's approaches do, although Keith reduces the number of boards to check by a factor of 4.
    + Optimisation: canonical representation. If we can check whether a board is in canonical representation much quicker than it takes to evaluate its score, we get a speed-up of a factor of about 8N^2. (There are also partial approaches with smaller equivalence classes).
    + Optimisation: DP. Cache the score for each board, so that rather than walking them through until they converge or diverge we just walk until we find a board we've seen before. In principle this would give a speed-up by a factor of the average score / cycle length (maybe 20 or more), but in practice we're likely to be swapping heavily. E.g. for N=6 we'd need capacity for 2^36 scores, which at a byte per score is 16GB, and we need random access so we can't expect good cache locality.
    + Combine the two. For N=6, the full canonical representation would allow us to reduce the DP cache to about 60 mega-scores. This is a promising approach.
* Brute force backwards. This seems odd at first, but if we assume that we can easily find still lifes and that we can easily invert the `Next(board)` function, we see that it has some benefits, although not as many as I originally hoped.
    + We don't bother with diverging boards at all. Not much of a saving, because they are quite rare.
    + We don't need to store scores for all of the boards, so there should be less memory pressure than the forward DP approach.
    + Working backwards is actually quite easy by varying a technique I saw in the literature in the context of enumerating still lifes. It works by treating each column as a letter in an alphabet and then observing that a sequence of three letters determines the middle one in the next generation. The parallel with enumerating still lifes is so close that I've refactored them together into an only slightly awkward method, `Prev2`.
    + It might seem that we can just canonicalise the still lifes, and get something like the 8N^2 speed-up for very little cost. However, empirically we still get a big reduction in the number of boards considered if we canonicalise at each step.
    + A surprisingly high proportion of boards have a score of 2 or 3, so there is still memory pressure. I found it necessary to canonicalise on the fly rather than building the previous generation and then canonicalising. It might be interesting to reduce memory usage by doing depth-first rather than breadth-first search, but doing so without overflowing the stack and without doing redundant calculations requires a co-routine / continuation approach to enumerating the previous boards.

I don't think that micro-optimisation will let me catch up with Keith's code, but for the sake of interest I'll post what I have. This solves N=5 in about a minute on a 2GHz machine using Mono 2.4 or .Net (without PLINQ) and in about 20 seconds using PLINQ; N=6 runs for many hours.

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

namespace Sandbox {
    class Codegolf9393 {
        internal static void Main() {
            new Codegolf9393(4).Solve();
        }

        private readonly int _Size;
        private readonly uint _AlphabetSize;
        private readonly uint[] _Transitions;
        private readonly uint[][] _PrevData1;
        private readonly uint[][] _PrevData2;
        private readonly uint[,,] _CanonicalData;

        private Codegolf9393(int size) {
            if (size > 8) throw new NotImplementedException("We need to fit the bits in a ulong");

            _Size = size;
            _AlphabetSize = 1u << _Size;

            _Transitions = new uint[_AlphabetSize * _AlphabetSize * _AlphabetSize];
            _PrevData1 = new uint[_AlphabetSize * _AlphabetSize][];
            _PrevData2 = new uint[_AlphabetSize * _AlphabetSize * _AlphabetSize][];
            _CanonicalData = new uint[_Size, 2, _AlphabetSize];

            InitTransitions();
        }

        private void InitTransitions() {
            HashSet<uint>[] tmpPrev1 = new HashSet<uint>[_AlphabetSize * _AlphabetSize];
            HashSet<uint>[] tmpPrev2 = new HashSet<uint>[_AlphabetSize * _AlphabetSize * _AlphabetSize];
            for (int i = 0; i < tmpPrev1.Length; i++) tmpPrev1[i] = new HashSet<uint>();
            for (int i = 0; i < tmpPrev2.Length; i++) tmpPrev2[i] = new HashSet<uint>();

            for (uint i = 0; i < _AlphabetSize; i++) {
                for (uint j = 0; j < _AlphabetSize; j++) {
                    uint prefix = Pack(i, j);
                    for (uint k = 0; k < _AlphabetSize; k++) {
                        // Build table for forwards checking
                        uint jprime = 0;
                        for (int l = 0; l < _Size; l++) {
                            uint count = GetBit(i, l-1) + GetBit(i, l) + GetBit(i, l+1) + GetBit(j, l-1) + GetBit(j, l+1) + GetBit(k, l-1) + GetBit(k, l) + GetBit(k, l+1);
                            uint alive = GetBit(j, l);
                            jprime = SetBit(jprime, l, (count == 3 || (alive + count == 3)) ? 1u : 0u);
                        }
                        _Transitions[Pack(prefix, k)] = jprime;

                        // Build tables for backwards possibilities
                        tmpPrev1[Pack(jprime, j)].Add(k);
                        tmpPrev2[Pack(jprime, i, j)].Add(k);
                    }
                }
            }

            for (int i = 0; i < tmpPrev1.Length; i++) _PrevData1[i] = tmpPrev1[i].ToArray();
            for (int i = 0; i < tmpPrev2.Length; i++) _PrevData2[i] = tmpPrev2[i].ToArray();

            for (uint col = 0; col < _AlphabetSize; col++) {
                _CanonicalData[0, 0, col] = col;
                _CanonicalData[0, 1, col] = VFlip(col);
                for (int rot = 1; rot < _Size; rot++) {
                    _CanonicalData[rot, 0, col] = VRotate(_CanonicalData[rot - 1, 0, col]);
                    _CanonicalData[rot, 1, col] = VRotate(_CanonicalData[rot - 1, 1, col]);
                }
            }
        }

        private ICollection<ulong> Prev2(bool stillLife, ulong next, ulong prev, int idx, ICollection<ulong> accum) {
            if (stillLife) next = prev;

            if (idx == 0) {
                for (uint a = 0; a < _AlphabetSize; a++) Prev2(stillLife, next, SetColumn(0, idx, a), idx + 1, accum);
            }
            else if (idx < _Size) {
                uint i = GetColumn(prev, idx - 2), j = GetColumn(prev, idx - 1);
                uint jprime = GetColumn(next, idx - 1);
                uint[] succ = idx == 1 ? _PrevData1[Pack(jprime, j)] : _PrevData2[Pack(jprime, i, j)];
                foreach (uint b in succ) Prev2(stillLife, next, SetColumn(prev, idx, b), idx + 1, accum);
            }
            else {
                // Final checks: does the loop round work?
                uint a0 = GetColumn(prev, 0), a1 = GetColumn(prev, 1);
                uint am = GetColumn(prev, _Size - 2), an = GetColumn(prev, _Size - 1);
                if (_Transitions[Pack(am, an, a0)] == GetColumn(next, _Size - 1) &&
                    _Transitions[Pack(an, a0, a1)] == GetColumn(next, 0)) {
                    accum.Add(Canonicalise(prev));
                }
            }

            return accum;
        }

        internal void Solve() {
            DateTime start = DateTime.UtcNow;
            ICollection<ulong> gen = Prev2(true, 0, 0, 0, new HashSet<ulong>());
            for (int depth = 1; gen.Count > 0; depth++) {
                Console.WriteLine("Length {0}: {1}", depth, gen.Count);
                ICollection<ulong> nextGen;

                #if NET_40
                nextGen = new HashSet<ulong>(gen.AsParallel().SelectMany(board => Prev2(false, board, 0, 0, new HashSet<ulong>())));
                #else
                nextGen = new HashSet<ulong>();
                foreach (ulong board in gen) Prev2(false, board, 0, 0, nextGen);
                #endif

                // We don't want the still lifes to persist or we'll loop for ever
                if (depth == 1) {
                    foreach (ulong stilllife in gen) nextGen.Remove(stilllife);
                }

                gen = nextGen;
            }
            Console.WriteLine("Time taken: {0}", DateTime.UtcNow - start);
        }

        private ulong Canonicalise(ulong board)
        {
            // Find the minimum board under rotation and reflection using something akin to radix sort.
            Isomorphism canonical = new Isomorphism(0, 1, 0, 1);
            for (int xoff = 0; xoff < _Size; xoff++) {
                for (int yoff = 0; yoff < _Size; yoff++) {
                    for (int xdir = -1; xdir <= 1; xdir += 2) {
                        for (int ydir = 0; ydir <= 1; ydir++) {
                            Isomorphism candidate = new Isomorphism(xoff, xdir, yoff, ydir);

                            for (int col = 0; col < _Size; col++) {
                                uint a = canonical.Column(this, board, col);
                                uint b = candidate.Column(this, board, col);

                                if (b < a) canonical = candidate;
                                if (a != b) break;
                            }
                        }
                    }
                }
            }

            ulong canonicalValue = 0;
            for (int i = 0; i < _Size; i++) canonicalValue = SetColumn(canonicalValue, i, canonical.Column(this, board, i));
            return canonicalValue;
        }

        struct Isomorphism {
            int xoff, xdir, yoff, ydir;

            internal Isomorphism(int xoff, int xdir, int yoff, int ydir) {
                this.xoff = xoff;
                this.xdir = xdir;
                this.yoff = yoff;
                this.ydir = ydir;
            }

            internal uint Column(Codegolf9393 _this, ulong board, int col) {
                uint basic = _this.GetColumn(board, xoff + col * xdir);
                return _this._CanonicalData[yoff, ydir, basic];
            }
        }

        private uint VRotate(uint col) {
            return ((col << 1) | (col >> (_Size - 1))) & (_AlphabetSize - 1);
        }

        private uint VFlip(uint col) {
            uint replacement = 0;
            for (int row = 0; row < _Size; row++)
                replacement = SetBit(replacement, row, GetBit(col, _Size - row - 1));
            return replacement;
        }

        private uint GetBit(uint n, int bit) {
            bit %= _Size;
            if (bit < 0) bit += _Size;

            return (n >> bit) & 1;
        }

        private uint SetBit(uint n, int bit, uint value) {
            bit %= _Size;
            if (bit < 0) bit += _Size;

            uint mask = 1u << bit;
            return (n & ~mask) | (value == 0 ? 0 : mask);
        }

        private uint Pack(uint a, uint b) { return (a << _Size) | b; }
        private uint Pack(uint a, uint b, uint c) {
            return (((a << _Size) | b) << _Size) | c;
        }

        private uint GetColumn(ulong n, int col) {
            col %= _Size;
            if (col < 0) col += _Size;
            return (_AlphabetSize - 1) & (uint)(n >> (col * _Size));
        }

        private ulong SetColumn(ulong n, int col, uint value) {
            col %= _Size;
            if (col < 0) col += _Size;

            ulong mask = (_AlphabetSize - 1) << (col * _Size);
            return (n & ~mask) | (((ulong)value) << (col * _Size));
        }
    }
}

```

# Answer
> 1 votes
# Factor

```
USING: arrays grouping kernel locals math math.functions math.parser math.order math.ranges math.vectors sequences sequences.extras ;
IN: longest-gof-pattern

:: neighbors ( x y game -- neighbors )
game length :> len
x y game -rot 2array {
    { -1 -1 }
    { -1 0 }
    { -1 1 }
    { 0 -1 }
    { 0 1 }
    { 1 -1 }
    { 1 0 }
    { 1 1 }
} [
    v+ [
        dup 0 <
        [ dup abs len mod - abs len mod ] [ abs len mod ]
        if
    ] map
] with map [ swap [ first2 ] dip nth nth ] with map ;

: next ( game -- next )
dup [
    [
        neighbors sum
        [ [ 1 = ] [ 2 3 between? ] bi* and ]
        [ [ 0 = ] [ 3 = ] bi* and ] 2bi or 1 0 ?
    ] curry curry map-index
] curry map-index ;

: suffixes ( seq -- suffixes )
{ }
[ [ [ suffix ] curry map ] [ 1array 1array ] bi append ]
reduce ;

! find largest repeating pattern
: LRP ( seq -- pattern )
dup length iota
[ 1 + [ reverse ] dip group [ reverse ] map reverse ] with
map dup [ dup last [ = ] curry map ] map
[ suffixes [ t [ and ] reduce ] map [ ] count ] map
dup supremum [ = ] curry find drop swap nth last ;

: game-sequence ( game -- seq )
1array [
    dup [
        dup length 2 >
        [ 2 tail-slice* [ first ] [ last ] bi = not ]
        [ drop t ] if
    ] [ LRP length 1 > not ] bi and
] [ dup last next suffix ] while ;

: pad-to-with ( str len padstr -- rstr )
[ swap dup length swapd - ] dip [ ] curry replicate ""
[ append ] reduce prepend ;

:: all-NxN-games ( n -- games )
2 n sq ^ iota [
    >bin n sq "0" pad-to-with n group
    [ [ 48 = 0 1 ? ] { } map-as ] map
] map ;

: longest-gof-pattern ( n -- game )
all-NxN-games [ game-sequence ] map [ length ] supremum-by but-last ;

```

Some time stats:

```
IN: longest-gof-pattern [ 3 longest-gof-pattern ] time dup length . .
Running time: 0.08850873500000001 seconds

3
{
   { { 1 1 1 } { 0 0 0 } { 0 0 0 } }
   { { 1 1 1 } { 1 1 1 } { 1 1 1 } }
   { { 0 0 0 } { 0 0 0 } { 0 0 0 } }
}

IN: longest-gof-pattern [ 4 longest-gof-pattern ] time dup length . .
Running time: 49.667698828 seconds

10
{
  { { 0 1 1 0 } { 0 1 0 0 } { 0 1 0 0 } { 1 1 0 1 } }
  { { 0 1 1 0 } { 0 1 0 0 } { 0 1 0 0 } { 0 0 0 1 } }
  { { 0 1 1 0 } { 0 1 0 0 } { 0 0 1 0 } { 1 1 0 0 } }
  { { 0 1 1 0 } { 0 1 0 0 } { 0 0 1 0 } { 0 0 0 1 } }
  { { 0 1 1 0 } { 0 1 0 0 } { 0 0 1 0 } { 1 1 0 1 } }
  { { 0 1 1 0 } { 0 1 0 0 } { 0 0 1 1 } { 0 0 0 1 } }
  { { 0 1 0 1 } { 0 1 0 1 } { 0 0 1 1 } { 1 1 0 1 } }
  { { 1 1 0 1 } { 1 1 0 1 } { 0 0 0 0 } { 1 1 0 0 } }
  { { 1 1 0 1 } { 1 1 0 1 } { 0 0 1 1 } { 1 1 1 1 } }
  { { 0 0 0 0 } { 0 0 0 0 } { 0 0 0 0 } { 0 0 0 0 } }
}

```

And testing 5 crashed the REPL. Hmph. The most inefficient portion of the program is probably the function game-sequence. I might be able to make it better later.

---
Tags: sequence, fastest-code, cellular-automata, busy-beaver, game-of-life
---


title: Make a pattern alternate

text:
# Question
Title: Make a pattern alternate
**Problem**

You are given a sequence of coloured balls (red `R` and green `G`). One such possible sequence is:

```
RGGGRRGGRGRRRGGGRGRRRG

```

In as few moves as possible, you must make it so that each ball is a different colour to its neighbours (i.e. the sequence alternates.)

```
RGRGRGRGRGRGRGRGRGRGRG

```

You should write a program that can convert an unordered sequence (in this case a string) with equal numbers of "R" and "G" into a sequence where the items alternate. One example session is below, for a naive algorithm (`<` is input to program, `>` is output. It isn't necessary to include the carets on the input or output.)

```
< RGGGRRGGRGRRRGGGRGRRRG
> RGGRGRGGRGRRRGGGRGRRRG
> RGRGGRGGRGRRRGGGRGRRRG
> RGRGRGGGRGRRRGGGRGRRRG
> RGRGRGGRGGRRRGGGRGRRRG
> RGRGRGGRGRGRRGGGRGRRRG
> RGRGRGGRGRGRGRGRGGRRRG
> RGRGRGGRGRGRGRGRGRGRRG
> RGRGRGGRGRGRGRGRGRGRGR
> RGRGRGRGGRGRGRGRGRGRGR
> RGRGRGRGRGGRGRGRGRGRGR
> RGRGRGRGRGRGGRGRGRGRGR
> RGRGRGRGRGRGRGGRGRGRGR
> RGRGRGRGRGRGRGRGGRGRGR
> RGRGRGRGRGRGRGRGRGGRGR
> RGRGRGRGRGRGRGRGRGRGGR
> RGRGRGRGRGRGRGRGRGRGRG (15 moves)

```

Another possibility is outputting "5,7" for example to indicate swapping of positions 5 and 7.

You may position *either* Red or Green first, and you don't have to be consistent. Each sequence will be the same length as every other sequence.

You may only swap any two letters in each move (they do not need to be adjacent.)

**Winning Criteria**

The program must show each step of the sort process. The program which makes the fewest *total* moves for all the below strings, wins. If there is a tie, the shortest code will win.

**Input Strings**

The following strings will be used to test the programs:

```
GGGGGGGGGGRRRRRRRRRR
GGRRGGRRGGRRGGRRGGRR
RRGGGGRRRRGGGGRRRRGG
GRRGRGGGGRRRGGGGRRRR
GRGGGRRRRGGGRGRRGGRR
RGRGRGRGRGRGRGRGRGRG

```

The last sequence should result in zero moves.

# Answer
## Python, 140 122 119 115

```
r=raw_input()
f=lambda x:[i for i in range(x,len(r),2)if x-(r[i]!=max('RG',key=r[::2].count))]
print zip(f(0),f(1))

```
> 5 votes

# Answer
## GolfScript (47 chars)

```
:S;4,{S,,{.S=1&3*\1&2*^1$=},\;}%2/{zip}%{,}$0=`

```

E.g. (using a test case which is far easier to check for correctness than any of the suggested ones, which all have lots of correct answers):

```
< RRGGRGRGRGRGRGRGRGRG
> [[1 2]]

```

Output is a list of zero-indexed pairs to swap.
> 3 votes

# Answer
## APL 46

```
((2|y)/y←(i≠↑i)/n),[.1](~2|y)/y←(i=↑i)/n←⍳⍴i←⍞

```

Running the given test cases yields:

```
GGGGGGGGGGRRRRRRRRRR
11 13 15 17 19
 2  4  6  8 10

GGRRGGRRGGRRGGRRGGRR
3 7 11 15 19
2 6 10 14 18

RRGGGGRRRRGGGGRRRRGG
3 5 11 13 19
2 8 10 16 18

GRRGRGGGGRRRGGGGRRRR
3 5 11 17 19
4 6  8 14 16

GRGGGRRRRGGGRGRRGGRR
7  9 13 15 19
4 10 12 14 18

RGRGRGRGRGRGRGRGRGRG

```

The above solution uses index origin 1 with the swaps given in the columns of the results matrix. Two characters can be saved if the input vector i is initialised with the input string prior to execution rather than being input at the time of execution.
> 3 votes

# Answer
## Python, 213 chars

```
I=raw_input()
def M(S,T):
 S=list(S);m=[]
 while S!=list(T):z=zip(S,T);x=z.index(('R','G'));y=z.index(('G','R'));m+=[(x,y)];S[x],S[y]='GR'
 return m
N=len(I)/2
x=M(I,N*'RG')
y=M(I,N*'GR')
print[x,y][len(x)>len(y)]

```

`M` finds the moves required to convert `S` to `T`. It does this by repeatedly finding an `R` and a `G` out of position and swapping them. We then find the shorter move sequence to get to either `RGRG...RG` or `GRGR...GR`.

Should find an optimal sequence of moves for every input.
> 2 votes

# Answer
# Mathematica 238

**Code**

```
f[x_] := With[{g = "GRGRGRGRGRGRGRGRGRGR", c = Characters, p = Position},
y = c[x]; s = c[g]; {v = Equal @@@ ({s, y}\[Transpose]),
w = Not /@ v}; {vv = Thread[{y, v}], ww = Thread[{y, w}]};
((Flatten /@ {p[#, {"R", False}], p[#, {"G", False}]}) &[If[Count[Equal @@@
({s, y}\[Transpose]), False] < 10, vv, ww]])\[Transpose]]

```

N.B.: `\[Transpose]` is a single character, a superscripted "t", in *Mathematica*\]

**Examples**

```
f@"GGGGGGGGGGRRRRRRRRRR"
f@"GGRRGGRRGGRRGGRRGGRR"
f@"RRGGGGRRRRGGGGRRRRGG"
f@"GRRGRGGGGRRRGGGGRRRR"
f@"GRGGGRRRRGGGRGRRGGRR"
f@"RGRGRGRGRGRGRGRGRGRG"
f@"GRGRGRGRGRGRGRGRGRGR"

```

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

# Answer
## Mathematica 134 or 124

Depending on how you count "Transpose\[\]" which on Mathematica is just one char (no representation here). Spaces added for clarity

```
G = 0; R = 1;
x_~ d ~ y__:= Transpose[Position[Symbol /@ Characters@x - PadLeft[{}, 20, {y}], #, 1] &
                                                                                /@ {1, -1}]
f = SortBy[{d[#, 0, 1], d[#, 1, 0]}, Length][[1]] &

```

Sample:

```
f@"GGGGGGGGGGRRRRRRRRRR"
f@"GGRRGGRRGGRRGGRRGGRR"
f@"RRGGGGRRRRGGGGRRRRGG"
f@"GRRGRGGGGRRRGGGGRRRR"
f@"GRGGGRRRRGGGRGRRGGRR"
f@"RGRGRGRGRGRGRGRGRGRG"
f@"GRGRGRGRGRGRGRGRGRGR"

```

Output

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

```
> 2 votes

# Answer
# Javascript - 173 characters

```
a=prompt(w=[[],[]]).split('');for(i=a.length,f=a[0];i--;)if(i%2<1&&a[i]!=f)w[0].push(i);else if(i%2>0&&a[i]==f)w[1].push(i);for(i=w[0].length;i--;)alert(w[0][i]+','+w[1][i])

```

A great challenge, kept me busy for some time.
Here the codes results for the test cases:

```
GGGGGGGGGGRRRRRRRRRR: [10, 1] [12, 3] [14, 5] [16, 7] [18, 9]
GGRRGGRRGGRRGGRRGGRR: [ 2, 1] [ 6, 5] [10, 9] [14,13] [18,17]
RRGGGGRRRRGGGGRRRRGG: [ 2, 1] [ 4, 7] [10, 9] [12,15] [18,17]
GRRGRGGGGRRRGGGGRRRR: [ 2, 3] [ 4, 5] [10, 7] [16,13] [18,15]
GRGGGRRRRGGGRGRRGGRR: [ 6, 3] [ 8, 9] [12,11] [14,13] [18,17]
RGRGRGRGRGRGRGRGRGRG:

```
> 2 votes

# Answer
# PHP - 34 moves - 193 characters

```
$l=strlen($a=$_GET["a"]);$n=$a[0]=="R"?"G":"R";while($i<$l){if($a[++$i]!=$n){echo$o."
";$o=$a=substr($a,0,$i).$n.preg_replace("/".$n."/",$n=="R"?"G":"R",substr($a,$i+1),1);}$n=$n=="R"?"G":"R";}

```

Might still try to improve this...

```
red_green.php?a=GGGGGGGGGGRRRRRRRRRR

GRGGGGGGGGGRRRRRRRRR
GRGRGGGGGGGGRRRRRRRR
GRGRGRGGGGGGGRRRRRRR
GRGRGRGRGGGGGGRRRRRR
GRGRGRGRGRGGGGGRRRRR
GRGRGRGRGRGRGGGGRRRR
GRGRGRGRGRGRGRGGGRRR
GRGRGRGRGRGRGRGRGGRR
GRGRGRGRGRGRGRGRGRGR

```
> 1 votes

---
Tags: code-challenge, sequence
---


# Question
Title: Arbitrary-Length Ternary Squarefree Words
A string is squarefree if it contains no substring twice in a row.

It is possible to have an arbitrarily long squarefree word using a 3-letter alphabet.

Write a program which accepts a positive integer n from stdin and prints any squarefree word of length n, using characters `A`, `B` and `C`.

Shortest code wins.

# Answer
> 4 votes
## GolfScript (40 27 chars)

```
~1,{.{!}%+}2$*1,/<{,65+}%n+

```

The approach is a trivial variant on one of those described in Wikipedia: the run-lengths of 1s in the Thue-Morse sequence.

If the extra trailing newline is unacceptable it can be removed at the cost of one character by replacing `n` with `''`.

# Answer
> 6 votes
## Python, 94

```
n=input()
x=[0]
exec"x+=[1-y for y in x];"*n
print''.join('ABC'[x[i+1]-x[i]]for i in range(n))

```

It uses the Thue–Morse sequence method from wikipedia.

Efficient version (100 chars):

```
n=input()
x=[0]
while x==x[:n]:x+=[1-y for y in x]
print''.join('ABC'[x[i+1]-x[i]]for i in range(n))

```

# Answer
> 4 votes
## Python, 129 125 119

Using John Leech's method as described on the linked wiki page.

```
s='A'
n=input()
while len(s)<=n:s=''.join('ABCBCACABBCAABCCABBCACABABCBCACABBCAABC'[ord(t)%5::3]for t in s)
print s[:n]

```

# Answer
> 3 votes
## Python2 - 112 chars

This is pretty inefficient. It generates a *much much much* longer string than required and then truncates it. For example the intermediate `s` for `n=7` is 62748517 (13n) characters long

```
s='A'
n=input()
exec"s=''.join('ABCBCACABBCAABCCABBCACABABCBCACABBCAABC'[ord(t)%5::3]for t in s);"*n
print s[:n]

```

# Answer
> 2 votes
# Mathematica 159 140 134

**Edit**: A complete rewrite, using recursion (`NestWhile`). Much faster and no wasted effort.

**Code**

```
g@n_:=StringTake[NestWhile[#~StringReplace~{"A"-> "ABCBACBCABCBA","B"-> "BCACBACABCACB",
     "C"->"CABACBABCABAC"}&,"ABC",StringLength[#]<n&],n]

```

**Usage**

It takes approximately 1/40 sec to generate a ternary square free word with one million characters.

```
g[10]
g[53]
g[506]
AbsoluteTiming[g[10^6];]

```

**Verifying**

`f` will test whether a string is square free.

```
f[s_]:=StringFreeQ[s, x__~~x__]

```

Checking the above outputs and one case in which the string "CC" appears.

```
f@Out[336]
f@Out[337]
f@Out[338]
f["ABCBACBCABCBABCACBACCABCACBCABACBABCABACBCACBACABCACBA"]

```

> True
> True
> True
> False

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


title: (simple) variable and scope simulator

text:
# Question
Title: (simple) variable and scope simulator
Based on this closed question on stack overflow, what is the shortest way to stimulate scope for variables in an input. For simplicity, `print` is replaced with `>`.

copying critical information from the linked source:

> `[` and `]` start and end a new scope.
>
> > Within scopes any changes to a variable outside of that scope is not permanent and is reverted when the scope has left, but the outer values are used to determine if a variable is undefined and its starting value.
>
> Input will always start with `[` and will end with matching `]`
> If its not defined then value should be `0`
> All input that is not a variable is a number with no decimal points. as in `10` or `582`
> `> a` means print the contents of `a`
> `a 10` assigns `10` to `a`
> `a b` assigns the contents of `b` to `a`
> Variables should be considered strings: `one 1` is valid syntax
> It is not required for the input to contain the print command `>`

**Note on scoring**:

```
You may chose how to input and output the "code", but it should be explained in the answer.

```

I answered this on the linked page in java, but I did not go for shortest code.
Comment any suggestions or questions, so I can improve my future posts. Shortest code by character wins. Good luck.

# Answer
## Python 2, 165

```
def f(v):
 while 1:
    s=raw_input().split()
    if'['in s:f(dict(v))
    elif']'in s:break
    elif'>'in s:print v.get(s[1],0)
    else:v[s[0]]=v.get(s[1],s[1])
raw_input()
f({})

```

Character count assumes tabs are used for the second level of indentation.
> 1 votes

---
Tags: code-golf
---