title: Try and make a completely fake reboot!

text:
# Question
Title: Try and make a completely fake reboot!
This challenge is simple. Write code that shows what looks exactly like a complete reboot of the computer. It must not show anything on-screen that shows it is not a full reboot and should end at the log-in screen you would get after rebooting.

**Rules**

1. You can choose any OS you like to imitate. For example you can reboot into Linux from Windows, Mac from Linux, or any other combination you choose.
2. The code should display the full reboot full-screen with no signs that it isn't real.
3. This is a popularity contest so the cooler it looks, the better it is.
4. The code must be completely harmless, perform no actual rebooting, and be easy to quit at any point.
5. If you need to use external images to make the reboot look more realistic, then your code should automatically grab them from the web.
6. Your code should be self-contained, only relying on standard freely available libraries or tools, and must be easily executable by reading the instructions you provide.

As it is a popularity contest, I will award the win to the answer with the highest number of votes on June 1, 2014.

---

Following a request to narrow the question, here is an additional rule, the system should imitate any version of Windows or the Mint, Ubuntu, Debian, Fedora, Archlinux or Mageia distributions of Linux or OS X. For extra coolness, you should shut down in one and open in the other.

Interested people may want to look at Pitch dark (Earth Hour remembrance) where a number of ways are suggested for using the full screen even when starting in an xterm.

# Answer
# zsh + coreutils + unclutter + amixer + xterm (Arch Linux)

I took the answer by @TheDoctor and ran with it. This version has many improvements, and is 99% convincing to an experienced user (me) on my Arch Linux system. I use Zsh since it has good array and floating-point number support.
Dependencies: **feh, unclutter, amixer, zsh, xterm**

**Improvements:**

1) Use the number printed in the first column by dmesg, which is the time since boot, (e.g. \[ 0.000000\] ) to determine the time to sleep. Without this it looks very unrealistic on my machine. These times are parsed before the loop (in an early call to sleep) since parsing inside the loop is too slow.

2) Don't print lines where time since boot is larger than 16 seconds. This specific number is machine-dependent, but the point is to avoid printing later dmesg-stuff that comes from inserting/removing usb sticks, etc. and is unrelated to booting.

3) Do all this in a fullscreen terminal window with black background and white text. Kudos to Mechanical Snail for this trick used in: Make a PNG image with "Hello World!" with programming APIs, in the shortest code possible

4) Mute the audio on shutdown, restore volume when script finishes.

5) Hide the mouse cursor, restore when script finishes.

6) Show BIOS and Syslinux splash screens.

**Run with:** xterm -fu -fg white -bg black -e '/usr/bin/zsh fake-reboot.sh'

**Code:**

```
#!/usr/bin/zsh
# Remove (undisplay) the mouse pointer
unclutter -idle 0 -jitter 255 &
# Since there is no easily-accessible (i.e. without being root) shutdown log, we
# fake these messages.
echo "The system is going down for maintenance NOW."
sleep 2.0
echo "[21656.404742] systemd[1]: Shutting down."
echo "[21656.404742] systemd[1]: Stopping Session 1 of user `id -u -n`."
echo "[21656.404742] systemd[1]: Stopped Session 1 of user `id -u -n`."
echo "[21656.404742] systemd[1]: Stopping Sound Card."
# For added effect, store volume and then mute sound
volume=`amixer -- sget Master | awk -F'[][]' 'END{print $2}'`
amixer -- sset Master 0% &> /dev/null
echo "[21656.404742] systemd[1]: Stopped target Sound Card."
sleep 0.5
echo "[21656.919792] systemd[1]: Stopping system-systemd\x2dfsck.slice."
echo "[21656.919792] systemd[1]: Removed slice system-systemd\x2dfsck.slice."
echo "[21656.919792] systemd[1]: Stopping system-netctl\x2difplugd.slice."
echo "[21656.919793] systemd[1]: Removed slice system-netctl\x2difplugd.slice."
echo "[21656.919793] systemd[1]: Stopping User Manager for UID `id -u`..."
sleep 0.7
echo "[21657.624741] systemd[1]: Stopping Graphical Interface."
echo "[21657.624742] systemd[1]: Stopped target Graphical Interface."
echo "[21657.624745] systemd[1]: Stopping Multi-User System."
sleep 0.9
echo "[21658.606561] systemd[1]: Stopped target Multi-User System."
echo "[21658.606562] systemd[1]: Stopping Paths."
echo "[21658.606562] systemd[1]: Stopped D-Bus System Message Bus."
echo "[21658.606562] systemd[1]: Stopped target Paths."
echo "[21658.606568] systemd[1]: Stopping Timers."
echo "[21658.606568] systemd[1]: Stopped target Timers."
echo "[21658.606568] systemd[1]: Stopping Sockets."
echo "[21658.606568] systemd[1]: Stopped target Sockets."
echo "[21658.606568] systemd[1]: Starting Shutdown."
echo "[21658.606571] systemd[1]: Reached target Shutdown."
echo "[21658.606571] systemd[1]: Starting Exit the Session..."
echo "[21658.606571] systemd[1]: Received SIGRTMIN+26 from PID 10988 (kill)."
echo "[21658.606571] systemd[1]: Deactivated swap."
sleep 0.4
echo "[21659.001741] systemd[1]: Starting Unmount All Filesystems."
echo "[21659.001742] systemd[1]: Unmounted /home."
echo "[21659.001742] systemd[1]: Reached target Unmount All Filesystems."
echo "[21659.001742] systemd[1]: Stopping Remount Root and Kernel File Systems..."
echo "[21659.001742] systemd[1]: Stopped Remount Root and Kernel File Systems."
echo "[21659.001743] systemd[1]: Reached target Shutdown."
echo "[21659.001743] systemd[1]: Starting Final Step."
echo "[21659.001743] systemd[1]: Reached target Final Step."
echo "[21659.001754] systemd[1]: Shutting down."
sleep 0.3
echo "[21659.304341] systemd-journal[250]: Journal stopped"
sleep 0.2
echo "System halted."
sleep 2
clear
sleep 1
# Get the BIOS splash screen and display it
wget http://pvv.ntnu.no/~asmunder/bios.jpg  &> /dev/null
feh -Z -x -F -N --force-aliasing bios.jpg &
pid=$! # Store PID of Feh, so we can kill it later
# While showing the BIOS splash, use the time to parse dmesg output into arrays
tim=`dmesg | awk '{print $2}' | sed 's/]//' | grep "[0-9][0-9][0-9][0-9][0-9]"`
tim=($=tim)
dmsg=("${(@f)$(dmesg)}")
sleep 2.5
kill $pid
sleep 0.5
# Get the Syslinux splash and display it
wget http://pvv.ntnu.no/~asmunder/syslinux.png  &> /dev/null
feh -Z -x -F -N --force-aliasing syslinux.png &
pid=$!
sleep 1.3
kill $pid
# Loop through the arrays we created. Calculate the time we have to wait before
# displaying this line. If the wait time is less than 0.1 sec, we skip waiting.
T1=0.0
T2=0.0
n=0
for d in $dmsg; do
  T1=$T2
  T2=${tim[$n]}
  ((dT = $T2-$T1))
  if (( $dT > 0.1));then
    sleep $dT
  fi
  echo $d
  if (( $T2 > 16.0 )); then
    break
  fi
  ((n=$n+1))
done
sleep 1
clear
# It's normally agetty that parses /etc/issue and handles escape codes in a
# special way. Thus we skip the first line of /etc/issue and do that manually.
echo "Arch Linux "`uname -r`" (tty1)"
tail -n +2 /etc/issue
echo `hostname`" login:"
sleep 10
# Reset the mouse pointer so it is visible again
unclutter -idle 5 -jitter 0 &
# Reset the audio volume
amixer -- sset Master $volume &> /dev/null

```
> 18 votes

# Answer
## Commodore 64

```
1?CHR$(147)
2?"    **** COMMODORE 64 BASIC V2 ****"
3?
4?" 64K RAM SYSTEM  38911 BASIC BYTES FREE"

```

The BASIC intepreter will display the `READY.` prompt automatically.
> 12 votes

# Answer
# Bash + Coreutils (Linux)

```
echo "The system is going down for maintenance NOW."
clear
sleep 5
dmesg|while read i; do echo "$i"; sleep 0.1; done
cat /etc/issue
login

```
> 10 votes

# Answer
# TI-Basic

```
AxesOff
GridOff
LabelOff
CoordOff
ClrDraw
DispGraph
ClrHome

```
> 10 votes

# Answer
# Windows 8

Shoddy attempt, I can't figure out how to auto full screen. I tried.

```
<!DOCTYPE html>
<html>
<body>

<iframe width="1600" height="900" src="http://www.youtube.com/embed/VgQ87b7muWs?start=510&end=524&autoplay=1" frameborder="0" allowfullscreen></iframe>

</body>
</html>

```
> 5 votes

# Answer
# Python / Pygame OSX

```
import pygame, time, os, urllib # Import Modules
pygame.init() # Initalise Pygame
pygame.mouse.set_visible(0) # Hide the Cursor
stdscr = pygame.display.set_mode((1280,800),pygame.FULLSCREEN) # Set up the display
stdscr.fill((255,255,255)) # Fill the screen white
urllib.urlretrieve("http://harrybeadle.github.io/FakeRestart/apple.bmp", "apple.bmp") # Get Apple Logo
urllib.urlretrieve("http://harrybeadle.github.io/FakeRestart/startup.wav", "startup.wav") # Get Startup Sound
time.sleep(1) # Wait for 1 second, screen still black
applelogo = pygame.image.load('apple.bmp').convert() # Load the Logo
pygame.mixer.music.load('startup.wav') # Load the Bung
stdscr.blit(applelogo,(580, 340)) # Blit the logo
pygame.mixer.music.play(1) # Play the sound
pygame.display.flip() # Flip the buffers
time.sleep(5) # Wait 5 seconds
pygame.quit() # Quit the pygame window
os.remove('apple.bmp') # Delete logo
os.remove('startup.wav') # Delete bung
os.system('/System/Library/CoreServices/"Menu Extras"/User.menu/Contents/Resources/CGSession -suspend') # Lock the Mac

```

Now Updated!

Features:

* Blank Screen
* White Screen w/ Apple Logo **and Bung Sound**
* Assets downloaded from GitHub using `urlib`
* Locks the user's Mac preserving any work using a terminal command and `os.system()`
> 3 votes

# Answer
This one does linux with parameters "quiet" and "init=/bin/sh"

```
#!/bin/sh
echo shutting down
sleep 1
clear
echo Press F12 to enter setup. #everyone forgets the BIOS
sleep 1
clear

```
> 2 votes

---
Tags: popularity-contest
---


title: Algorithmic braiding - for mother's day

text:
# Question
Title: Algorithmic braiding - for mother's day
**Task:**

Your task is to create a program that, when given a number of strands and number of iterations of a braid, will tell where each strand goes. Rules are as follows:

* The number of strands will always be odd, and between 3 and 6000 (inclusive)
* When you start, the strands will be divided into 2 (almost) equal bunches, the `left` and the `right`. The `left` will have one more strand when you start.

For an input of 7:

```
/ / / / \ \ \
1 2 3 4 5 6 7

```
* Every iteration, the outermost strand of the side with more strands will be put in the center facing the opposite direction. The center is defined as between opposite facing strands: `////middle\\\`.

1 iteration of input 7 (strand 1 was moved to the center):

```
/ / / \ \ \ \
2 3 4 1 5 6 7

```

**Example:**

Input:

```
3 4

```

Computations:

```
1 2 3
 \
2 1 3
   /
2 3 1
 \
3 2 1
   /
3 1 2

```

Output:

```
3 1 2

```

**Rules:**

* You do not need to display the slashes for strand direction, only the numbers.
* You only need to display the numbers after the last iteration.
* Your output will be space-deliminated ids of the strands
* Input will be in the form: `strands [space] iterations`
* The number of strands will always be odd, and 3\<=x\<=6000
* This is , so the shortest code wins!

# Answer
### GolfScript, 33 characters

```
~\),(@{:^1$[=]:y-.,2//y*^~}*;' '*

```

The input must be provided on stdin.

Examples (you may test online):

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

> 3 4
3 1 2

> 11 2
2 3 4 5 6 11 1 7 8 9 10

```
> 6 votes

# Answer
### Python: 179 240, 152 characters

**First, the 179**

For `N` strands and `i` iterations, this answer uses `O(1)` space and `O(N)` time. I simply compute the end position of each strand, never iterating over the intermediate positions!

**big edit:** golfed this answer by changing conditionals to boolean algebra. I also wrote a lengthy explanation of how it works. TL;DR: formulaic patterns, modulo division.

```
from sys import *
N,i=map(int,stdin.readline().split())
h,t=N/2,3*N
f=lambda p:(p>N)*(t/2-(p&-2))+p/2+1
for s in xrange(N):print f((2*s+1+(s>h)*(t-4*s-2)+i*(N+1-N*(s!=h)))%(2*N)),

```

**Now the 152**

This is more reasonably golfed python. (edit: thanks to Alex Thornton for editing from 165 to 152)

```
from sys import*;l=map;r=range;n,m=l(int,stdin.readline().split());b=r(1,n+1)
for k in r(m):v=b.pop((0,n-1)[k%2]);b.insert(n/2,v)
print' '.join(l(str,b)

```
> 6 votes

# Answer
# Python 2 (109) / Python 3 (121)

**Python 2**

```
s,n=map(int,raw_input().split())
b=range(s)
for i in range(n):b[s/2:s/2]=[b.pop(0-i%2)]
for x in b:print x+1,

```

**Python 3**

```
s,n=map(int,input().split())
b=list(range(s))
for i in range(n):b[s//2:s//2]=[b.pop(0-i%2)]
for x in b:print(x+1,end=' ')

```

The code must have been bribed by Python 2 to showcase its golfing advantages over Python 3: ranges being lists, division rounding down to an int, print not starting a newline. The weird `0-i%2` is because `-i%2` evaluates as `(-i)%2`.

There's probably a more efficient approach than iterating, namely computing each final result directly. The braiding operation has period 2\*s, so it can't be that complicated.
> 2 votes

# Answer
## Ruby, 105

Just a lot of set manipulation. Push, pop, reverse and shift! I tried not converting inputs to integers, but it added about 20 characters.

```
n,i=$*.map(&:to_i)
f=l=(1..n).to_a
t=r=l.pop(n/2).reverse
i.times{f,t=t<<f.shift,f}
$><<(l+r.reverse)*' '

```

`l` and `r` (`left` and `right`) are the "thread" queues. `right` is reversed so we start pulling from the outside.

`t` and `f` (`to` and `from`) start off as `right` and `left`, respectively, but as we go we keep swapping them so we can always shift the last "thread" from `from` and push it to `to` (`f,t=t<<f.shift,f`). This saves a LOT of space.

Then we just re-reverse `right` at the end.

### Changelog:

2.2 **105** oh yeah, map can take a proc

2.1 **108** And actually, just flip things as part of manipulation.

2.0 **116** don't use that temporary array. Instead use two pointer variables we can manipulate and keep re-pointing. Then only display the end

1.0 **123** initial idea
> 2 votes

# Answer
## Java, 270 chars

golfed:

```
import java.util.*;class B{public static void main(String[] a){int n=Integer.valueOf(a[0]),t=Integer.valueOf(a[1]),i=0;List<Integer> r=new ArrayList<Integer>();for(;i<n;i++){r.add(i+1);}for(i=0;i<t;i++){int k=i%2==0?0:n-1;r.add(n/2,r.remove(k));}System.out.println(r);}}

```

un-golfed:

```
import java.util.*;
public class Braid {
    public static void main(String[] args) {
        int num = Integer.valueOf(args[0]);
        int iterations = Integer.valueOf(args[1]);

        //populate array
        List<Integer> arr = new ArrayList<Integer>();
        for (int i=0; i < num; i++) {
            arr.add(i+1);
        }
        for (int i=0; i < iterations; i++) {
            int index = i%2==0?0:num-1;
            arr.add(num/2, arr.remove(index));
        }
        System.out.println(arr);
    }
}

```

Run online
> 0 votes

---
Tags: code-golf
---


title: Duct Tape some sorting

text:
# Question
Title: Duct Tape some sorting
Your job is to make a sorting algorithm. The catch, you must copy it from Stack Overflow.

Your program will take an input array (or equivalency), and output a sorted permutation of the array.

* Your program must consist solely of copy and pasted code blocks from Stack Overflow.
* You may not take parts of a code block, nor may you rearrange one. A code block is everything within a single gray box.
* The original question of the post may not have a tag, title, or question body containing the word "sort" in it.
* You must cite the both the post and poster(s).
* You may not use built in sorts.
* The post must be older than this question.

Also, here are allowed modifications:

* You may move import statements to the top
* For any type of identifier type thing, you may replace **all** of its occurrences within the code block with a different name. Please list substitutions.

This is a popularity contest, so the correct answer with the most up-votes wins!

# Answer
# GolfScript

Straightforward bubble sort implementation. Can probably be golfed down further. Try it online.

```
~x {{ document.write man [
putc( 'c', stdout ) ;
\b {{ return 1 echo ${10}
return
true;
Convert.ToDouble(o)
datagrid1.ItemsSource = dataTable1.DefaultView;
echo $a:u
cat > file {{ \b }} ~x
int* arr1[8];
}}
source ~/.bashrc
return
true;
] document.write
@echo off
IP=`curl ifconfig.me`
return
true;
~x return !0
return
true;
}} ~x
for {0..10..2}; do
  ..
done
set -x
\b
basename `pwd`
~x

```

### Sources

https://stackoverflow.com/a/2513659 (https://stackoverflow.com/u/276101):

`~x`

https://stackoverflow.com/a/3773868 (https://stackoverflow.com/u/394167):

`{{`

https://stackoverflow.com/a/802894 (https://stackoverflow.com/u/8815):

`document.write`

https://stackoverflow.com/a/2188223 (https://stackoverflow.com/u/116908):

`man [`

https://stackoverflow.com/q/4563825 (https://stackoverflow.com/u/111307):

```
putc( 'c', stdout ) ;

```

https://stackoverflow.com/a/16876671 (https://stackoverflow.com/u/980550):

`\b`

https://stackoverflow.com/a/22604291 (https://stackoverflow.com/u/1622022):

`return 1`

https://stackoverflow.com/a/6146038 (https://stackoverflow.com/u/116908):

`echo ${10}`

https://stackoverflow.com/a/4054267 (https://stackoverflow.com/u/69083):

```
return
true;

```

https://stackoverflow.com/q/23657401 (https://stackoverflow.com/u/1171811):

`Convert.ToDouble(o)`

https://stackoverflow.com/q/6097907 (https://stackoverflow.com/u/517871):

```
datagrid1.ItemsSource = dataTable1.DefaultView;

```

https://stackoverflow.com/a/4813101 (https://stackoverflow.com/u/591720):

```
echo $a:u

```

https://stackoverflow.com/q/19114714 (https://stackoverflow.com/u/72436):

`cat > file`

https://stackoverflow.com/a/3773868 (https://stackoverflow.com/u/394167):

`}}`

https://stackoverflow.com/a/859676 (https://stackoverflow.com/u/87234):

```
int* arr1[8];

```

https://stackoverflow.com/a/2518150 (https://stackoverflow.com/u/245602):

```
source ~/.bashrc

```

https://stackoverflow.com/a/5750751 (https://stackoverflow.com/u/187690):

`]`

https://stackoverflow.com/q/8823643 (https://stackoverflow.com/u/1059446):

```
@echo off

```

https://stackoverflow.com/a/9764597 (https://stackoverflow.com/u/167925):

```
IP=`curl ifconfig.me`

```

https://stackoverflow.com/a/8255667 (https://stackoverflow.com/u/179669):

`return !0`

https://stackoverflow.com/a/966110 (https://stackoverflow.com/u/104162):

```
for {0..10..2}; do
  ..
done

```

https://stackoverflow.com/a/6930980 (https://stackoverflow.com/u/705676):

```
set -x

```

https://stackoverflow.com/a/4641636 (https://stackoverflow.com/u/333698):

```
basename `pwd`

```
> 5 votes

---
Tags: popularity-contest, sorting, duct-tape-coding
---


# Question
Title: Encode a string for aliens that read and write English, but don't know ASCII
Turns out there are some distant aliens who know English *(and have coincidentally standardized on 8-bit computer architectures)*. Yet they have never heard of ASCII, nor even alphabetical order.

It is believed that these aliens are picking up information from Earth. Yet they are doing so with digital equipment that reads meaningless information when no transmission is being sent...thus the signal must be contained in a way to stand out from surrounding noise.

A new standard has been created, modeled after the Arecibo Message's use of a semiprime signal length:

# Universal Semiotic Coding for Information Interchange (USCII)

*(See: http://uscii.hostilefork.com)*

In USCII, each code is derived from a bitmap representing the character, that has a prime width and a prime height. For instance, this 5x7 representation of a letter A:

```
01110
10001
10001
10001
11111
10001
10001

```

That produces 35 bits. Yet in order to make even single-character messages stand out from the noise and look coherent, strings are embedded in a container format that helps reinforce the prime factors. The container has been chosen to also make it easy to manipulate the strings on architectures that operate on multiples of 8 bits.

With its container, the "A" above would look like:

```
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
1111111111111111111111111111111111100000
1111111111111111111111111111111111100000
1111111111111111111111111111111111100000
1111111111111111111111111111111111100000
1111111111111111111111111111111111100000
0111010001100011000111111100011000100000
1111111111111111111111111111111111100000
1111111111111111111111111111111111100000
1111111111111111111111111111111111100000
1111111111111111111111111111111111100000
1111111111111111111111111111111111100000
1111111111111111111111111111111111100000
1111111111111111111111111111111111100000
1111111111111111111111111111111111111111
1111111111111111111111111111111111111111
1111111111111111111111111111111111111111
1111111111111111111111111111111111111111
1111111111111111111111111111111111111111

```

The characters of the message are first prefixed with five solid 5x7 bitmaps, and seven solid 5x7 bitmaps added to the end. (The **"meter"**.) Then each of these have five 0 bits tacked onto the end to make an even 40 bits.

Finally there are 7 all-zero 40-bit runs added to the beginning, and 5 all-one 40-bit runs added to the end. (The **"silence"**.)

# Your mission

You are to write an encoder. Input is a conventional ASCII string typed from the keyboard. The bitmaps you will use are from the 5x7 PIC CPU font.

*(Note: It's easy enough to extract the font from the page for all the talented code golfers here, but if you want those bytes all together here they are.)*

Output should be a printed string in hexadecimal.

# Examples

**Input**:

```
ABCDEFG

```

**Output**:

`0000000000000000000000000000000000000000000000000000000000000000000000FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0FFFFFFFFE074631FC620F463E8C7C074610845C0E4A318CB80FC21E843E0FC21E84200746178C5E0FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF`

**Input**:

```
Dear aliens: Please get me off of this planet!!!

```

**Output**:

`0000000000000000000000000000000000000000000000000000000000000000000000FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0E4A318CB80001D1FC1E0001C17C5E0002D9842000000000000001C17C5E061084211C00100421080001D1FC1E0002D98C620001F0707C003180630000000000000F463E8420061084211C0001D1FC1E0001C17C5E0001F0707C0001D1FC1E00000000000001F1787C0001D1FC1E0213E421440000000000000375AD620001D1FC1E00000000000001D18C5C01148E210801148E210800000000000001D18C5C01148E210800000000000213E4214408421E8C6200100421080001F0707C00000000000003D1F420061084211C0001C17C5E0002D98C620001D1FC1E0213E421440210840008021084000802108400080FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF`

# Clarifications

# Winning Conditions

`0000000000000000000000000000000000000000000000000000000000000000000000FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0FFFFFFFFE074610845C0001D18C5C00842F8C5E0001D1FC1E00000000000746178C5E0001D18C5C061084211C01148E21080210840008021084000802108400080FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0FFFFFFFFE0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF`

# Answer
> 3 votes
# Python 2, ~~671~~ ~~669~~ 663 bytes

```
D=str.decode
d=D(D("eJxNUmsSHiEIuxIgvn76sXr/IzVB26kzqyxCCBGRt0xlOM5RbXp6qv32Omu6lT22nTGiOVe05muMFXM11ZuuynwV52f8E7W11+SdzGMvTl6GHvm3ig6RRBbp3nqNqGEFeACK7m5YZYPAMMGV6qyk4ydKKD3FTPeAcQZhUAw4lh4aR8YcWaaVV480lDTJF64thyT4T+8tCjVofOtLnKInAAYDyJ0e9lxj+wJk/MYJ0nBQvYaRhnbQQEIrB5t1fX2VwdMnZF1zLF/Gf2H62PtXGYwypU5msXo2mNUvclE+QXqY3sNkg3GcKReKRTPrGnizNNCOw+tenSWaLQZf6VC926UYVw7I0y/eDEOo/LfKvvLdEQjt7NTzLXrkI2MmNrMPRYDng4a6VR0ThTKMgUA9XlYzTIsk+XtCH+y2mk1rf6VD4V7Xh2Cxb2YWkdkprlDCTR6yv5jnQSuQScEb0CBu5WXZ1ScN6gMDvWa73HNoy845VMg7wLBlA9wwhAMTiNn6ravFH00dtSc=","base64"),"zip")
i=raw_input()
m="F"*8+"E0"
o="0"*70+m*5
for c in i:x=ord(c)*9-288;o+=d[x:x+9]+"0"
print o+m*7+"F"*50

```

---

# PHP with zlib, ~~738~~ ~~716~~ 715 bytes

```
<?php $d=gzinflate(base64_decode("TVJrEh4hCLsSIL5++rF6/yM1QdupM6ssQggRkbdMZTjOUW16eqr99jprupU9tp0xojlXtOZrjBVzNdWbrsp8Fedn/BO1tdfkncxjL05ehh75t4oOkUQW6d56jahhBXgAiu5uWGWDwDDBleqspOMnSig9xUz3gHEGYVAMOJYeGkfGHFmmlVePNJQ0yReuLYck+E/vLQo1aHzrS5yiJwAGA8idHvZcY/sCZPzGCdJwUL2GkYZ20EBCKwebdX19lcHTJ2Rdcyxfxn9h+tj7VxmMMqVOZrF6NpjVL3JRPkF6mN7DZINxnCkXikUz6xp4szTQjsPrXp0lmi0GX+lQvdulGFcOyNMv3gxDqPy3yr7y3REI7ezU8y165CNjJjazD0WA54OGulUdE4UyjIFAPV5WM0yLJPl7Qh/stppNa3+lQ+Fe14dgsW9mFpHZKa5Qwk0esr+Y50ErkEnBG9AgbuVl2dUnDeoDA71mu9xzaMvOOVTIO8CwZQPcMIQDE4jZ+q2rxR8="));$i=trim(fgets(STDIN));$f="str_repeat";echo $f(0,70).$f($m="FFFFFFFFE0",5);foreach(str_split($i)as$c)echo substr($d,ord($c)*9-288,9)."0";echo $f($m,7).$f("F",50);

```

First, your PHP needs to be configured with `--with-zlib`. And run this script from command line, like `php 26972.php`. This program takes input from STDIN.

(If `short_open_tag=On`, I can save 3 more bytes.)

## Ungolfed

```
<?php
$data = gzinflate(base64_decode("TVJrEh4hCLsSIL5++rF6/yM1QdupM6ssQggRkbdMZTjOUW16eqr99jprupU9tp0xojlXtOZrjBVzNdWbrsp8Fedn/BO1tdfkncxjL05ehh75t4oOkUQW6d56jahhBXgAiu5uWGWDwDDBleqspOMnSig9xUz3gHEGYVAMOJYeGkfGHFmmlVePNJQ0yReuLYck+E/vLQo1aHzrS5yiJwAGA8idHvZcY/sCZPzGCdJwUL2GkYZ20EBCKwebdX19lcHTJ2Rdcyxfxn9h+tj7VxmMMqVOZrF6NpjVL3JRPkF6mN7DZINxnCkXikUz6xp4szTQjsPrXp0lmi0GX+lQvdulGFcOyNMv3gxDqPy3yr7y3REI7ezU8y165CNjJjazD0WA54OGulUdE4UyjIFAPV5WM0yLJPl7Qh/stppNa3+lQ+Fe14dgsW9mFpHZKa5Qwk0esr+Y50ErkEnBG9AgbuVl2dUnDeoDA71mu9xzaMvOOVTIO8CwZQPcMIQDE4jZ+q2rxR8="));
$input = trim(fgets(STDIN));
$f = "str_repeat";

echo $f(0, 70).$f($m = "FFFFFFFFE0", 5);
foreach(str_split($input) as $c)
    echo substr($data, ord($c) * 9 - 288, 9)."0";
echo $f($m, 7).$f("F", 50);

```

# Answer
> 2 votes
**C**

This actually prints human readable hex (vs binary for readablity). Everything is represented in unsigned long long and only 9-10 hex digits are used due (depending whether you include the 00000 padding) the unfortunate 6x5 format (an 8x4 font would have just been too easy)

```
#include <stdio.h>
#define u unsigned long long
void p(int n, u x){while(n--) printf("%09llX",x);}
int main(void){
char *s="ABCDEFG";
u a[128]={0xAAAAAAAAAULL,0xADEB7ADEAULL,0xDFF7FDFF6ULL,0xDEF7BDFF6ULL,0xFFFFFFCE6ULL,0xFF41DB82EULL,0xFD7FF747EULL,0xDC63107F6ULL,0xFEEE0BEFEULL,0x0003D0800ULL,0xE1084FB88ULL,0x21084201CULL,0xFB880FB88ULL,0x084ADFB08ULL,0x25F7BDF78ULL,0xE777BDDC8ULL,0xFFC8E27FEULL,0xFDE719DFEULL,0xDED4A73A2ULL,0xFD6B5AD7EULL,0xFC6318C7EULL,0xFD7FF8BBEULL,0xFFFFFFABEULL,0xF81CA703EULL,0x881445022ULL,0xFC58A347EULL,0x8BBDDDFF6ULL,0x1995E73A2ULL,0xAD6B5AD6AULL,0xDEF7BDEF6ULL,0xF7B5204F6ULL,0xFFFFF9EEEULL,0x000000000ULL,0x210840008ULL,0x529400000ULL,0x52BEAFA94ULL,0x23E8E2F88ULL,0xC644444C6ULL,0x64A88AC9AULL,0x611000000ULL,0x111084104ULL,0x410421110ULL,0x012AEA900ULL,0x0109F2100ULL,0x000006110ULL,0x0001F0000ULL,0x000000318ULL,0x004444400ULL,0x74675CC5CULL,0x23084211CULL,0x74422223EULL,0xF88820C5CULL,0x11952F884ULL,0xFC3C10C5CULL,0x3221E8C5CULL,0xF84444210ULL,0x7462E8C5CULL,0x7462F0898ULL,0x031806300ULL,0x031806110ULL,0x111104104ULL,0x003E0F800ULL,0x410411110ULL,0x744222008ULL,0x7442DAD5CULL,0x74631FC62ULL,0xF463E8C7CULL,0x74610845CULL,0xE4A318CB8ULL,0xFC21E843EULL,0xFC21E8420ULL,0x746178C5EULL,0x8C63F8C62ULL,0x71084211CULL,0x388421498ULL,0x8CA98A4A2ULL,0x84210843EULL,0x8EEB58C62ULL,0x8C7359C62ULL,0x746318C5CULL,0xF463E8420ULL,0x74631AC9AULL,0xF463EA4A2ULL,0x7C20E087CULL,0xF90842108ULL,0x8C6318C5CULL,0x8C6318A88ULL,0x8C631AD54ULL,0x8C5445462ULL,0x8C62A2108ULL,0xF8444443EULL,0x72108421CULL,0x000000000ULL,0x70842109CULL,0x22A200000ULL,0x00000003EULL,0x410400000ULL,0x001C17C5EULL,0x8421E8C7CULL,0x001F0841EULL,0x0842F8C5EULL,0x001D1FC1EULL,0x1148E2108ULL,0x001F1787CULL,0x8421E8C62ULL,0x010042108ULL,0x100421498ULL,0x4212A6292ULL,0x61084211CULL,0x00375AD62ULL,0x002D98C62ULL,0x001D18C5CULL,0x003D1F420ULL,0x001F17842ULL,0x002D98420ULL,0x001F0707CULL,0x213E42144ULL,0x002318C5CULL,0x002318A88ULL,0x00231AD54ULL,0x0022A22A2ULL,0x0022A2110ULL,0x003E2223EULL,0x190882106ULL,0x210802108ULL,0xC10822130ULL,0x0BA000000ULL,0xFE2A2AE3EULL};
p(7,0ULL);
p(5,0xFFFFFFFE0ULL);
while(*s)p(1,a[*s++]);
p(7,0xFFFFFFFE0ULL);
p(5,0xFFFFFFFFFULL);
return 0;
}

```

**bash**

```
#!/bin/sh
p(){
i=0
while ([ $i -lt $1 ]) do
printf $2
i=$((i+1))
done
}

t(){
#Given string input $1, go char by char & create "alien" representation

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

j=0
p 7 0000000000
p 5 FFFFFFFFE0
while ([ "${j}" -lt "${#1}" ]) do
   i=${C%${1:$j:1}*}
   i=${#i}
   printf ${A:$(( $i*10 )):10}
   j=$(($j+1))
done
p 7 FFFFFFFFE0
p 5 FFFFFFFFFF
}
t "Dear aliens: Please get me off of this planet!!!"

```

# Answer
> 2 votes
# PHP, 874 bytes

You will need to run this script from the command line (`php uscii.php`) because it takes input from stdin.

```
<?php $f=base64_decode(str_replace('@','AA','@@@QhC@RSl@AClfV9SiPo4viYyIiJjZKiKyawi@@REIQQSCCEIiAEq6p@IT5C@@GEQ@Pg@@@xgAiIiAHRnXMXEYQhCOdEIiI/8RBBi4RlS+IX4eCGLjIh6MXfCIiEIdGLoxc6MXhEwDGAYwAGMAwiBERBBBAB8HwAQQQREQ6IREAR0QtrVzoxj+MfRj6MfOjCEIu5KMYy5+EPQh/8IehCDowvGL4xj+MYuIQhCOOIQhSZGVMUlGEIQhD8d1rGMYxzWcYujGMYu9GPoQg6MY1k30Y+pKL4QcEPvkIQhCRjGMYujGMYqJGMY1qqMVEVGMYxUQhPhEREPuQhCEOBBBBBA4QhCE4iog@@@AH0EE@@A4L4vhCHox8AD4Qg8IQvjF4AOj+DxFI4hC@+Lw+hCHoxiAgCEIQQBCFJiEJUxSWEIQhHAButaxAC2YxiADoxi4APR9C@Pi8IQAtmEI@+Dg+IT5CFEAEYxi4AIxiogARjWqgAioiogBFRCIAD4iI+MhEEIMhCAIQmCEEQmAug@@='));$a=trim(fgets(STDIN));$r='str_repeat';echo$r('0',70).$r($q='FFFFFFFFE0',5);foreach(str_split($a)as$c){$v=(ord($c)-32)*35;$x=$v>>3;$y=1<<(7-$v%8);$b=0;for($i=0;$i<40;$i++){$b+=$b+($i<35&&ord($f[$x])&$y);if(($i&7)==7)$b=!printf('%02X',$b);if(!($y>>=1)&&$x++)$y=128;}}echo$r($q,7).$r('F',50);

```

## Ungolfed:

```
<?php

// Font bitmap data rearranged as 95 consecutive 35-bit strings and padded
// out to 416 bytes with zeros:
$f=base64_decode(str_replace('@','AA',
    '@@@QhC@RSl@AClfV9SiPo4viYyIiJjZKiKyawi@@REIQQSCCEIiAEq6p@IT5C@@GEQ@Pg'.
    '@@@xgAiIiAHRnXMXEYQhCOdEIiI/8RBBi4RlS+IX4eCGLjIh6MXfCIiEIdGLoxc6MXhEw'.
    'DGAYwAGMAwiBERBBBAB8HwAQQQREQ6IREAR0QtrVzoxj+MfRj6MfOjCEIu5KMYy5+EPQh'.
    '/8IehCDowvGL4xj+MYuIQhCOOIQhSZGVMUlGEIQhD8d1rGMYxzWcYujGMYu9GPoQg6MY1'.
    'k30Y+pKL4QcEPvkIQhCRjGMYujGMYqJGMY1qqMVEVGMYxUQhPhEREPuQhCEOBBBBBA4Qh'.
    'CE4iog@@@AH0EE@@A4L4vhCHox8AD4Qg8IQvjF4AOj+DxFI4hC@+Lw+hCHoxiAgCEIQQB'.
    'CFJiEJUxSWEIQhHAButaxAC2YxiADoxi4APR9C@Pi8IQAtmEI@+Dg+IT5CFEAEYxi4AIx'.
    'iogARjWqgAioiogBFRCIAD4iI+MhEEIMhCAIQmCEEQmAug@@='));

// Fetch input:
$a=trim(fgets(STDIN));

// Header:
$r='str_repeat';
echo $r('0',70).$r($q='FFFFFFFFE0',5);

// Convert each input character into its corresponding hex sequence:
foreach (str_split($a) as $c) {
  $v=(ord($c)-32)*35;
  $x=$v>>3;
  $y=1<<(7-$v%8);
  $b=0;
  for ($i=0;$i<40;$i++) {
    // When $i>34, pad with zeros
    $b += $b + ($i<35 && ord($f[$x]) & $y);
    if (($i&7)==7) $b=!printf('%02X',$b); // print out $b and set $b=0
    // Shift mask to next bit position
    if (!($y>>=1)&&$x++) $y=128;
  }
}

// Tail:
echo $r($q,7).$r('F',50);

```

# Answer
> 2 votes
## JavaScript ES6 (838 Bytes)

```
_="z='00000';r=(n,m)=>m.repean);fop=prompi=o=';i<p.length;)o+=parseInatob('RSlClfV9SiPo4viYyIiJjZKiKyawiRQQSCCEq6pGEQPgxgAiIHRnXMXEYOdiI/8Ri4RlS+IX4eCGLjIhXfCIidGLcXhEwDGAYwAGMAwiBERBAB8HwAQQQREQ6IREAR0QtrVzj+MfRjfOjCu5KMYy5+EP/8IeDowvGL4xj+MYuIOOISZGVMUlGD8d1rxzWcYuju9GPoQgY1k30Y+pKL4QcEPvkIRjujqJ1qqMVEVxUPhEREPuEOBA4E4H0EEA4L4vH8AD4Qg8IQvjF4AOj+DxFI4+Lw+HgCQQBCFJiEJUxSWHAButaxAC2YxDi4APR9CPi8IQAtm+Dg+FEAEYxi4AIxARjWqgAioBFRCIAD4iI+MhEMAIQmCEEQmAugRV8nyE.split   p(e=>e028)).join    tch(/.{35}/g)[pi++)-32]+z,21610);14,z5,y='E0+o.toUpperCase(7,y5,10,'F)A.charCodeAQhGMY).toString(EI)).slice(-)+ ('.maC')hCoxiog(z+z+t(r(iABB6MFFAIT5C";for(Y in $=" ")with(_.split($[Y]))_=join(pop());eval(_)

```

Not crushed :

```
z='00000';r=(n,m)=>m.repeat(n);for(p=prompt(i=o='');i<p.length;)o+=(z+z+parseInt(atob('AAAAAAQhCAARSlAAAClfV9SiPo4viYyIiJjZKiKyawiAAAAREIQQSCCEIiAEq6pAAIT5CAAAAGEQAAPgAAAAAAxgAiIiAHRnXMXEYQhCOdEIiI/8RBBi4RlS+IX4eCGLjIh6MXfCIiEIdGLoxc6MXhEwDGAYwAGMAwiBERBBBAB8HwAQQQREQ6IREAR0QtrVzoxj+MfRj6MfOjCEIu5KMYy5+EPQh/8IehCDowvGL4xj+MYuIQhCOOIQhSZGVMUlGEIQhD8d1rGMYxzWcYujGMYu9GPoQg6MY1k30Y+pKL4QcEPvkIQhCRjGMYujGMYqJGMY1qqMVEVGMYxUQhPhEREPuQhCEOBBBBBA4QhCE4iogAAAAAAAH0EEAAAAA4L4vhCHox8AD4Qg8IQvjF4AOj+DxFI4hCAA+Lw+hCHoxiAgCEIQQBCFJiEJUxSWEIQhHAButaxAC2YxiADoxi4APR9CAAPi8IQAtmEIAA+Dg+IT5CFEAEYxi4AIxiogARjWqgAioiogBFRCIAD4iI+MhEEIMhCAIQmCEEQmAugAAARV8nyE').split('').map(e=>(z+z+e.charCodeAt(0).toString(2)).slice(-8)).join('').match(/.{35}/g)[p.charCodeAt(i++)-32]+z,2).toString(16)).slice(-10);r(14,z)+r(5,y='FFFFFFFFE0')+o.toUpperCase()+r(7,y)+r(5,r(10,'F'))

```

---
Tags: code-golf, encoding
---


title: King of the Hill: Speed Clue AI

text:
# Question
Title: King of the Hill: Speed Clue AI
## Speed Clue

Cluedo/Clue is a classic board game with a compelling deduction gameplay component. Speed Clue is a 3-6 player variant that emphasizes this component by using only the cards. The result is that the only difference between standard Cluedo and Speed Clue is that each player still in the game may make any suggestion he pleases on his turn instead of waiting to reach a specific room at the mercy of dice rolls and other players' suggestions. If you have never played Cluedo before, or want to be certain of the explicit differences between the two versions, you may find a complete Speed Clue rule set here.

---

## Goal

Write and submit an AI program to play Speed Clue before 15 May 2014 00:00 GMT. After that time, I will run a tournament using all the legal entries. The entrant whose AI wins the most games in the tournament wins the challenge.

---

## AI Specifications

You can write your AI in pretty much any language you choose, using whatever techniques you use, so long as it strictly uses the application protocol over a TCP/IP connection to play games with the server. A detailed explanation of all the restrictions can be found here.

---

## How to Play

Start by forking the contest GitHub repository. Add a directory under the `entries` directory named using your StackExchange user name, and develop your code in that folder. When you are ready to submit your entry, make a pull request with your revisions, then follow these instructions for announcing your entry on this site.

I have provided some code and JARs in the `core` directory for getting you started; see my site for a rough guide for the materials. In addition, other players are submitting helper code in addition to their entries to help you get up and running. Take some time to explore the entries, and don't forget to test your entry against others' entries before submitting!

---

## Results

```
Place | User         | AI                 | Result
------+--------------+--------------------+-------------------------------------------------------
    1 | gamecoder    | SpockAI            | 55.75%
    2 | Peter Taylor | InferencePlayer    | 33.06%
    3 | jwg          | CluePaddle         | 20.19%
    4 | Peter Taylor | SimpleCluedoPlayer |  8.34%
    5 | gamecoder    | RandomPlayer       |  1.71%
 ---- | ray          | 01                 | Player "ray-01" [3] sent an invalid accuse message: ""

```

The results above show the win percentage each qualified AI had of the 25,200 valid matches in which it participated. There were 30,000 matches in total that counted toward the results, and 6,100 or so that were discounted when `01` was disqualified.

An honorable mention needs to go to ray's `01` AI. My initial testing showed that it was the strongest, and I expected it to win the competition. However, it appears to have a very intermittent bug that, as far as I can guess, leads it to eliminate all possible solutions. The tournament had finished all the three-player matches and had started the four player matches (12,000 games in!) when `01`'s bug was revealed. If I just consider the 3-player match standings, the results look like this:

```
Place | User         | AI                 | Result
------+--------------+--------------------+--------
    1 | ray          | 01                 | 72.10%
    2 | gamecoder    | SpockAI            | 51.28%
    3 | Peter Taylor | InferencePlayer    | 39.97%
    4 | Peter Taylor | SimpleCluedoPlayer | 17.65%
    5 | jwg          | CluePaddle         | 16.92%
    6 | gamecoder    | RandomPlayer       |  2.08%

```

I had planned on doing some data mining on the results, but I am exhausted. I had technical difficulties in getting the competition to run all the way through (power failures, system reboots) that necessitated completely rewriting the contest server to save its progress as it proceeded. I will comment and commit all the changes to the code with all the results files that were generated in case anyone is still interested. If I decide to do the data mining as well, my results will also be added to the repository.

---

## Thanks for Playing!

# Answer
> 4 votes
## SpockAI

**Identifier:** `gamecoder-SpockAI`

**Repo Entry:** click here

**Selected:** Yes

**Technology:** Java 7 based upon `com.sadakatsu.clue.jar`

**Arguments:** `{identifier} portNumber [logOutput: true|false]`

**Description:**

`SpockAI` is a Speed Clue player built upon a class called `Knowledge` that I wrote. The `Knowledge` class represents all the possible states that the game could have given what has happened thus far. It represents the game's solutions and players' possible hands as sets, and uses iterative deductions to reduce these sets as far as possible every time something is learned. `SpockAI` uses this class to determine which suggestions are assured to have the most helpful worst-case results and randomly selects one of those suggestions on its turns. When it needs to disprove a suggestion, it tries to either show a card it has already shown the suggesting AI or to show it a card from the category for which it has reduced the possibilities the least. It only makes an accusation when it knows the solution.

The heuristic I used for determining the best suggestion is as follows. After all information has been learned from a suggestion, the possible solution and possible player hand sets will have been reduced (unless the suggestion reveals no new information). Theoretically, the best suggestion is the one that most reduces the number of possible solutions. In the case of a tie, I assume that a suggestion that most reduces the number of possible hands for players is better. So, for each suggestion, I try every possible outcome that does not lead to a contradiction in knowledge. Whichever outcome has the least improvement in solution/hand counts is assumed to be the result the suggestion will have. Then I compare all the suggestions' results, and pick which one has the best result. In this way, I guarantee optimal worst-case information gain.

I am considering adding a brute force combination analysis of possible solutions and possible player hands to make `SpockAI` even stronger, but since `SpockAI` is already the slowest, most resource-intensive entry, I will probably skip that.

**Disclaimer:**

I had intended to release an AI for this contest weeks ago. As it stands, I wasn't able to start writing my AI until Friday last week, and I kept finding ridiculous bugs in my code. Because of this, the only way I was able to get `SpockAI` to work before the deadline was to use a large thread pool. The end result is that (currently) SpockAI can hit +90% CPU utilization and 2GB+ memory usage (though I blame the garbage collector for this). I intend to run `SpockAI` in the contest, but if others feel that is a violation of the rules, I will award the title of "winner" to second place should `SpockAI` win. If you you feel this way, please leave a comment to that effect on this answer.

# Answer
> 5 votes
# AI01 - Python 3

I can't find a better name for it yet :-P .

**Identifier**: ray-ai01

**Technology**: Python 3

**Selected**: yes

**Arguments**: `ai01.py identifier port`

**Description**: Work by inference. When the number of cards that the owner is not known is less than a threshold, this AI starts to eliminate all impossible solutions by recursive global inference. Otherwise, it use local inference.

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

from speedclue.playerproxy import Player, main
from speedclue.cards import CARDS
from speedclue.protocol import BufMessager

# import crash_on_ipy

class Card:
    def __init__(self, name, type):
        self.name = name
        self.possible_owners = []
        self.owner = None
        self.in_solution = False
        self.disproved_to = set()
        self.type = type

    def __repr__(self):
        return self.name

    def log(self, *args, **kwargs):
        pass

    def set_owner(self, owner):
        assert self.owner is None
        assert self in owner.may_have
        for player in self.possible_owners:
            player.may_have.remove(self)
        self.possible_owners.clear()
        self.owner = owner
        owner.must_have.add(self)
        self.type.rest_count -= 1

    def set_as_solution(self):
        # import pdb; pdb.set_trace()
        assert self.owner is None
        self.type.solution = self
        self.in_solution = True
        for player in self.possible_owners:
            player.may_have.remove(self)
        self.possible_owners.clear()
        self.type.rest_count -= 1

    def __hash__(self):
        return hash(self.name)

class CardType:
    def __init__(self, type_id):
        self.type_id = type_id
        self.cards = [Card(name, self) for name in CARDS[type_id]]
        self.rest_count = len(self.cards)
        self.solution = None

class PlayerInfo:
    def __init__(self, id):
        self.id = id
        self.must_have = set()
        self.may_have = set()
        self.selection_groups = []
        self.n_cards = None

    def __hash__(self):
        return hash(self.id)

    def set_have_not_card(self, card):
        if card in self.may_have:
            self.may_have.remove(card)
            card.possible_owners.remove(self)

    def log(self, *args, **kwargs):
        pass

    def update(self):
        static = False
        updated = False
        while not static:
            static = True
            if len(self.must_have) == self.n_cards:
                if not self.may_have:
                    break
                for card in self.may_have:
                    card.possible_owners.remove(self)
                self.may_have.clear()
                static = False
                updated = True
            if len(self.must_have) + len(self.may_have) == self.n_cards:
                static = False
                updated = True
                for card in list(self.may_have):
                    card.set_owner(self)

            new_groups = []
            for group in self.selection_groups:
                group1 = []
                for card in group:
                    if card in self.must_have:
                        break
                    if card in self.may_have:
                        group1.append(card)
                else:
                    if len(group1) == 1:
                        group1[0].set_owner(self)
                        updated = True
                        static = False
                    elif group1:
                        new_groups.append(group1)
            self.selection_groups = new_groups

            if len(self.must_have) + 1 == self.n_cards:
                # There is only one card remain to be unknown, so this card must
                # be in all selection groups
                cards = self.may_have.copy()
                for group in self.selection_groups:
                    if self.must_have.isdisjoint(group):
                        cards.intersection_update(group)

                for card in self.may_have - cards:
                    static = False
                    updated = True
                    self.set_have_not_card(card)

        # assert self.must_have.isdisjoint(self.may_have)
        # assert len(self.must_have | self.may_have) >= self.n_cards
        return updated

class Suggestion:
    def __init__(self, player, cards, dplayer, dcard):
        self.player = player
        self.cards = cards
        self.dplayer = dplayer
        self.dcard = dcard
        self.disproved = dplayer is not None

class AI01(Player):
    def prepare(self):
        self.set_verbosity(0)

    def reset(self, player_count, player_id, card_names):
        self.log('reset', 'id=', player_id, card_names)
        self.fail_count = 0
        self.suggest_count = 0
        self.card_types = [CardType(i) for i in range(len(CARDS))]
        self.cards = list(itertools.chain(*(ct.cards for ct in self.card_types)))
        for card in self.cards:
            card.log = self.log
        self.card_map = {card.name: card for card in self.cards}
        self.owned_cards = [self.card_map[name] for name in card_names]
        self.players = [PlayerInfo(i) for i in range(player_count)]
        for player in self.players:
            player.log = self.log
        self.player = self.players[player_id]
        for card in self.cards:
            card.possible_owners = list(self.players)
        n_avail_cards = len(self.cards) - len(CARDS)
        for player in self.players:
            player.may_have = set(self.cards)
            player.n_cards = n_avail_cards // player_count \
                + (player.id < n_avail_cards % player_count)
        for card in self.owned_cards:
            card.set_owner(self.player)
        for card in self.cards:
            if card not in self.owned_cards:
                self.player.set_have_not_card(card)
        self.suggestions = []
        self.avail_suggestions = set(itertools.product(*CARDS))
        self.possible_solutions = {
            tuple(self.get_cards_by_names(cards)): 1
            for cards in self.avail_suggestions
        }
        self.filter_solutions()

    def filter_solutions(self):
        new_solutions = {}
        # assert self.possible_solutions
        join = next(iter(self.possible_solutions))
        for sol in self.possible_solutions:
            for card, type in zip(sol, self.card_types):
                if card.owner or type.solution and card is not type.solution:
                    # This candidate can not be a solution because it has a
                    # card that has owner or this type is solved.
                    break
            else:
                count = self.check_solution(sol)
                if count:
                    new_solutions[sol] = count
                    join = tuple(((x is y) and x) for x, y in zip(join, sol))
        self.possible_solutions = new_solutions
        updated = False
        for card in join:
            if card and not card.in_solution:
                card.set_as_solution()
                updated = True
                self.log('found new target', card, 'in', join)

        # self.dump()
        return updated

    def check_solution(self, solution):
        """
        This must be called after each player is updated.
        """
        players = self.players
        avail_cards = set(card for card in self.cards if card.possible_owners)
        avail_cards -= set(solution)
        if len(avail_cards) >= 10:
            return 1
        count = 0

        def resolve_player(i, avail_cards):
            nonlocal count
            if i == len(players):
                count += 1
                return
            player = players[i]
            n_take = player.n_cards - len(player.must_have)
            cards = avail_cards & player.may_have
            for choice in map(set, itertools.combinations(cards, n_take)):
                player_cards = player.must_have | choice
                for group in player.selection_groups:
                    if player_cards.isdisjoint(group):
                        # Invalid choice
                        break
                else:
                    resolve_player(i + 1, avail_cards - choice)

        resolve_player(0, avail_cards)
        return count

    def suggest1(self):
        choices = []
        for type in self.card_types:
            choices.append([])
            if type.solution:
                choices[-1].extend(self.player.must_have & set(type.cards))
            else:
                choices[-1].extend(sorted(
                    (card for card in type.cards if card.owner is None),
                    key=lambda card: len(card.possible_owners)))

        for sgi in sorted(itertools.product(*map(lambda x:range(len(x)), choices)),
                key=sum):
            sg = tuple(choices[i][j].name for i, j in enumerate(sgi))
            if sg in self.avail_suggestions:
                self.avail_suggestions.remove(sg)
                break
        else:
            sg = self.avail_suggestions.pop()
            self.fail_count += 1
            self.log('fail')
        self.suggest_count += 1
        return sg

    def suggest(self):
        sg = []
        for type in self.card_types:
            card = min((card for card in type.cards if card.owner is None),
                key=lambda card: len(card.possible_owners))
            sg.append(card.name)
        sg = tuple(sg)

        if sg not in self.avail_suggestions:
            sg = self.avail_suggestions.pop()
        else:
            self.avail_suggestions.remove(sg)
        return sg

    def suggestion(self, player_id, cards, disprove_player_id=None, card=None):
        sg = Suggestion(
            self.players[player_id],
            self.get_cards_by_names(cards),
            self.players[disprove_player_id] if disprove_player_id is not None else None,
            self.card_map[card] if card else None,
        )
        self.suggestions.append(sg)
        # Iter through the non-disproving players and update their may_have
        end_id = sg.dplayer.id if sg.disproved else sg.player.id
        for player in self.iter_players(sg.player.id + 1, end_id):
            if player is self.player:
                continue
            for card in sg.cards:
                player.set_have_not_card(card)
        if sg.disproved:
            # The disproving player has sg.dcard
            if sg.dcard:
                if sg.dcard.owner is None:
                    sg.dcard.set_owner(sg.dplayer)
            else:
                # Add a selection group to the disproving player
                sg.dplayer.selection_groups.append(sg.cards)
            self.possible_solutions.pop(tuple(sg.cards), None)

        self.update()

    def update(self):
        static = False
        while not static:
            static = True
            for card in self.cards:
                if card.owner is not None or card.in_solution:
                    continue
                if len(card.possible_owners) == 0 and card.type.solution is None:
                    # In solution
                    card.set_as_solution()
                    static = False

            for type in self.card_types:
                if type.solution is not None:
                    continue
                if type.rest_count == 1:
                    card = next(card for card in type.cards if card.owner is None)
                    card.set_as_solution()
                    static = False

            for player in self.players:
                if player is self.player:
                    continue
                if player.update():
                    static = False

            if self.filter_solutions():
                static = False

    def iter_players(self, start_id, end_id):
        n = len(self.players)
        for i in range(start_id, start_id + n):
            if i % n == end_id:
                break
            yield self.players[i % n]

    def accuse(self):
        if all(type.solution for type in self.card_types):
            return [type.solution.name for type in self.card_types]
        possible_solutions = self.possible_solutions
        if len(possible_solutions) == 1:
            return next(possible_solutions.values())
        # most_possible = max(self.possible_solutions, key=self.possible_solutions.get)
        # total = sum(self.possible_solutions.values())
        # # self.log('rate:', self.possible_solutions[most_possible] / total)
        # if self.possible_solutions[most_possible] > 0.7 * total:
        #     self.log('guess', most_possible)
        #     return [card.name for card in most_possible]
        return None

    def disprove(self, suggest_player_id, cards):
        cards = self.get_cards_by_names(cards)
        sg_player = self.players[suggest_player_id]
        cards = [card for card in cards if card in self.owned_cards]
        for card in cards:
            if sg_player in card.disproved_to:
                return card.name
        return max(cards, key=lambda c: len(c.disproved_to)).name

    def accusation(self, player_id, cards, is_win):
        if not is_win:
            cards = tuple(self.get_cards_by_names(cards))
            self.possible_solutions.pop(cards, None)
            # player = self.players[player_id]
            # for card in cards:
            #     player.set_have_not_card(card)
            # player.update()
        else:
            self.log('fail rate:', self.fail_count / (1e-8 + self.suggest_count))
            self.log('fail count:', self.fail_count, 'suggest count:', self.suggest_count)

    def get_cards_by_names(self, names):
        return [self.card_map[name] for name in names]

    def dump(self):
        self.log()
        for player in self.players:
            self.log('player:', player.id, player.n_cards,
                sorted(player.must_have, key=lambda x: x.name),
                sorted(player.may_have, key=lambda x: x.name),
                '\n    ',
                player.selection_groups)
        self.log('current:', [type.solution for type in self.card_types])
        self.log('possible_solutions:', len(self.possible_solutions))
        for sol, count in self.possible_solutions.items():
            self.log('  ', sol, count)
        self.log('id|', end='')

        def end():
            return ' | ' if card.name in [g[-1] for g in CARDS] else '|'

        for card in self.cards:
            self.log(card.name, end=end())
        self.log()
        for player in self.players:
            self.log(' *'[player.id == self.player.id] + str(player.id), end='|')
            for card in self.cards:
                self.log(
                    ' ' + 'xo'[player in card.possible_owners or player is card.owner],
                    end=end())
            self.log()

if __name__ == '__main__':
    main(AI01, BufMessager)

```

The AI code can be found here.

# Answer
> 4 votes
## SimpleCluedoPlayer.java

This class uses `AbstractCluedoPlayer`, which handles all the I/O and lets the logic work with a simple typed interface. The whole thing is on github.

This beats the random player with high probability (in the worst case it takes 15 suggestions, whereas the random player takes an average of 162), but it will be easily beaten. I offer it to get the ball rolling.

```
package org.cheddarmonk.cluedoai;

import java.io.IOException;
import java.io.PrintStream;
import java.net.UnknownHostException;
import java.util.*;

/**
 * A simple player which doesn't try to make inferences from partial information.
 * It merely tries to maximise the information gain by always making suggestions involving cards which
 * it does not know to be possessed by a player, and to minimise information leakage by recording who
 * has seen which of its own cards.
 */
public class SimpleCluedoPlayer extends AbstractCluedoPlayer {
    private Map<CardType, Set<Card>> unseenCards;
    private Map<Card, Integer> shownBitmask;
    private Random rnd = new Random();

    public SimpleCluedoPlayer(String identifier, int serverPort) throws UnknownHostException, IOException {
        super(identifier, serverPort);
    }

    @Override
    protected void handleReset() {
        unseenCards = new HashMap<CardType, Set<Card>>();
        for (Map.Entry<CardType, Set<Card>> e : Card.byType.entrySet()) {
            unseenCards.put(e.getKey(), new HashSet<Card>(e.getValue()));
        }

        shownBitmask = new HashMap<Card, Integer>();
        for (Card myCard : myHand()) {
            shownBitmask.put(myCard, 0);
            unseenCards.get(myCard.type).remove(myCard);
        }
    }

    @Override
    protected Suggestion makeSuggestion() {
        return new Suggestion(
            selectRandomUnseen(CardType.SUSPECT),
            selectRandomUnseen(CardType.WEAPON),
            selectRandomUnseen(CardType.ROOM));
    }

    private Card selectRandomUnseen(CardType type) {
        Set<Card> candidates = unseenCards.get(type);
        Iterator<Card> it = candidates.iterator();
        for (int idx = rnd.nextInt(candidates.size()); idx > 0; idx--) {
            it.next();
        }
        return it.next();
    }

    @Override
    protected Card disproveSuggestion(int suggestingPlayerIndex, Suggestion suggestion) {
        Card[] byNumShown = new Card[playerCount()];
        Set<Card> hand = myHand();
        int bit = 1 << suggestingPlayerIndex;
        for (Card candidate : suggestion.cards()) {
            if (!hand.contains(candidate)) continue;

            int bitmask = shownBitmask.get(candidate);
            if ((bitmask & bit) == bit) return candidate;
            byNumShown[Integer.bitCount(bitmask)] = candidate;
        }

        for (int i = byNumShown.length - 1; i >= 0; i--) {
            if (byNumShown[i] != null) return byNumShown[i];
        }

        throw new IllegalStateException("Unreachable");
    }

    @Override
    protected void handleSuggestionResponse(Suggestion suggestion, int disprovingPlayerIndex, Card shown) {
        if (shown != null) unseenCards.get(shown.type).remove(shown);
        else {
            // This player never makes a suggestion with cards from its own hand, so we're ready to accuse.
            unseenCards.put(CardType.SUSPECT, Collections.singleton(suggestion.suspect));
            unseenCards.put(CardType.WEAPON, Collections.singleton(suggestion.weapon));
            unseenCards.put(CardType.ROOM, Collections.singleton(suggestion.room));
        }
    }

    @Override
    protected void recordSuggestionResponse(int suggestingPlayerIndex, Suggestion suggestion, Card shown) {
        shownBitmask.put(shown, shownBitmask.get(shown) | (1 << suggestingPlayerIndex));
    }

    @Override
    protected void recordSuggestionResponse(int suggestingPlayerIndex, Suggestion suggestion, int disprovingPlayerIndex) {
        // Do nothing.
    }

    @Override
    protected Suggestion makeAccusation() {
        Set<Card> suspects = unseenCards.get(CardType.SUSPECT);
        Set<Card> weapons = unseenCards.get(CardType.WEAPON);
        Set<Card> rooms = unseenCards.get(CardType.ROOM);
        if (suspects.size() * weapons.size() * rooms.size()  == 1) {
            return new Suggestion(suspects.iterator().next(), weapons.iterator().next(), rooms.iterator().next());
        }

        return null;
    }

    @Override
    protected void recordAccusation(int accusingPlayer, Suggestion accusation, boolean correct) {
        // Do nothing.
    }

    //*********************** Public Static Interface ************************//
    public static void main(String[] args) throws Exception {
        try {
            System.setOut(new PrintStream("/tmp/speed-cluedo-player" + args[0]+".log"));
            new SimpleCluedoPlayer(args[0], Integer.parseInt(args[1])).run();
        } catch (Throwable th) {
            th.printStackTrace(System.out);
        }
    }
}

```

# Answer
> 3 votes
## InferencePlayer.java

Full code on Github (note: this uses the same `AbstractCluedoPlayer` as my earlier `SimpleCluedoPlayer`).

The true core of this player is its `PlayerInformation` class (here slightly trimmed):

```
private static class PlayerInformation {
    final PlayerInformation[] context;
    final int playerId;
    final int handSize;
    Set<Integer> clauses = new HashSet<Integer>();
    Set<Card> knownHand = new HashSet<Card>();
    int possibleCards;
    boolean needsUpdate = false;

    public PlayerInformation(PlayerInformation[] context, int playerId, boolean isMe, int handSize, Set<Card> myHand) {
        this.context = context;
        this.playerId = playerId;
        this.handSize = handSize;
        if (isMe) {
            knownHand.addAll(myHand);
            possibleCards = 0;
            for (Card card : knownHand) {
                int cardMask = idsByCard.get(card);
                clauses.add(cardMask);
                possibleCards |= cardMask;
            }
        }
        else {
            possibleCards = allCardsMask;
            for (Card card : myHand) {
                possibleCards &= ~idsByCard.get(card);
            }

            if (playerId == -1) {
                // Not really a player: this represents knowledge about the solution.
                // The solution contains one of each type of card.
                clauses.add(suspectsMask & possibleCards);
                clauses.add(weaponsMask & possibleCards);
                clauses.add(roomsMask & possibleCards);
            }
        }
    }

    public void hasCard(Card card) {
        if (knownHand.add(card)) {
            // This is new information.
            needsUpdate = true;
            clauses.add(idsByCard.get(card));

            // Inform the other PlayerInformation instances that their player doesn't have the card.
            int mask = idsByCard.get(card);
            for (PlayerInformation pi : context) {
                if (pi != this) pi.excludeMask(mask);
            }

            if (knownHand.size() == handSize) {
                possibleCards = mask(knownHand);
            }
        }
    }

    public void excludeMask(int mask) {
        if (knownHand.size() == handSize) return; // We can't benefit from any new information.

        if ((mask & possibleCards) != 0) {
            // The fact that we have none of the cards in the mask contains some new information.
            needsUpdate = true;
            possibleCards &= ~mask;
        }
    }

    public void disprovedSuggestion(Suggestion suggestion) {
        if (knownHand.size() == handSize) return; // We can't benefit from any new information.

        // Exclude cards which we know the player doesn't have.
        needsUpdate = clauses.add(mask(suggestion.cards()) & possibleCards);
    }

    public void passedSuggestion(Suggestion suggestion) {
        if (knownHand.size() == handSize) return; // We can't benefit from any new information.

        excludeMask(mask(suggestion.cards()));
    }

    public boolean update() {
        if (!needsUpdate) return false;

        needsUpdate = false;

        // Minimise the clauses, step 1: exclude cards which the player definitely doesn't have.
        Set<Integer> newClauses = new HashSet<Integer>();
        for (int clause : clauses) {
            newClauses.add(clause & possibleCards);
        }
        clauses = newClauses;

        if (clauses.contains(0)) throw new IllegalStateException();

        // Minimise the clauses, step 2: where one clause is a superset of another, discard the less specific one.
        Set<Integer> toEliminate = new HashSet<Integer>();
        for (int clause1 : clauses) {
            for (int clause2 : clauses) {
                if (clause1 != clause2 && (clause1 & clause2) == clause1) {
                    toEliminate.add(clause2);
                }
            }
        }
        clauses.removeAll(toEliminate);

        // Every single-card clause is a known card: update knownHand if necessary.
        for (int clause : clauses) {
            if (((clause - 1) & clause) == 0) {
                Card singleCard = cardsById.get(clause);
                hasCard(cardsById.get(clause));
            }
        }

        // Every disjoint set of clauses of size equal to handSize excludes all cards not in the union of that set.
        Set<Integer> disjoint = new HashSet<Integer>(clauses);
        for (int n = 2; n <= handSize; n++) {
            Set<Integer> nextDisjoint = new HashSet<Integer>();
            for (int clause : clauses) {
                for (int set : disjoint) {
                    if ((set & clause) == 0) nextDisjoint.add(set | clause);
                }
            }
            disjoint = nextDisjoint;
        }

        for (int set : disjoint) excludeMask(~set);

        return true;
    }
}

```

It unifies information on suggestions which the player didn't disprove (indicating that they hold none of those cards), suggestions which they did disprove (indicating that they hold at least one of those cards), and cards whose location is certain. Then it iteratively applies some basic rules to compact that information into its essence.

I don't think there's any more deterministic information to be obtained (except from via false accusations, which I'm assuming to be too rare to bother with), although I may have overlooked something. There *is* potential for a more sophisticated player to estimate probabilities that player X has card Y...

The other area which probably admits significant improvement is in deciding which suggestion to make. I attempt to maximise the information gain using a fairly clunky heavy-force approach, but there's a lot of poorly justified heuristic in evaluating the relative merits of the knowledge gained from different hypothetical disproofs. However, I'm not going to try tuning the heuristics until someone else posts a worthy opponent.

# Answer
> 2 votes
# CluePaddle (ClueStick / ClueBat / ClueByFour) - C#

I have written ClueBot, a C# client for which it is straightforward to implement AIs, and various AIs, including the most serious attempt called CluePaddle. The code is at https://github.com/jwg4/SpeedClueContest/tree/clue\_paddle with a pull request started to merge it into upstream.

ClueStick is a proof-of-concept which basically just guesses and ignores most of what happens. ClueBat is another stupid AI, except that it tries to exploit a flaw in ClueStick to force it to do false accusations. ClueByFour is a reasonable AI in that it makes reasonable suggestions and remembers the cards it is shown by others.

CluePaddle is the most intelligent. It tries to figure out who has what based not only on what disproofs have been offered, but also based on which players didn't offer a disproof of a given suggestion. It doesn't take into account how many cards each player has atm but this is to be fixed. It includes a couple of quite long classes so I won't post the whole code here, but the following method gives a flavor.

```
public void Suggestion(int suggester, MurderSet suggestion, int? disprover, Card disproof)
{
  List<int> nonDisprovers = NonDisprovers(suggester, disprover).ToList();

  foreach (var player in nonDisprovers)
  {
    m_cardTracker.DoesntHaveAnyOf(player, suggestion);
  }

  if (disprover != null && disproof == null)
  {
    // We know who disproved it but not what they showed.
    Debug.Assert(disprover != m_i, "The disprover should see the disproof");
    Debug.Assert(suggester != m_i, "The suggester should see the disproof");
    m_cardTracker.DoesntHaveAllOf(suggester, suggestion);
    m_cardTracker.HasOneOf((int)disprover, suggestion);
  }

  if (disproof != null)
  {
    // We know who disproved it and what they showed.
    Debug.Assert(disprover != null, "disproof is not null but disprover is null");
    m_cardTracker.DoesHave((int)disprover, disproof.Value);
  }
}

```

If the 4 play against each other, CluePaddle wins by far the most games, with ClueByFour second and the other two nowhere.

**Only CluePaddle is a competitive entry (so far).** Usage:

```
CluePaddle.exe identifier port

```

If anyone else wants to make a C# AI, just create a ConsoleApplication project in the soltution, implement the `IClueAI` interface in a class, and then make your `Program` derive from `ProgramTemplate` and copy what the other projects do for `Main()`. The only dependency is NUnit for unit testing and you could easily remove all the testing from the code (but don't, just install NUnit).

---
Tags: king-of-the-hill, board-game
---


# Question
Title: Find the smallest illegal (probable) prime
An illegal prime is a prime number which encodes information that is illegal to possess - specifically, in one case, a gzip file of the source code of DeCSS, a piece of software to decrypt copy-protected DVDs.

Your task has two phases:

1. Build a source file that implements DeCSS in as few bytes as possible. This can be done in any language.
2. Compress this source file (using your favourite compression algorithm), and iterate through possible files that decompress to the same thing (using Dirichlet's theorem if it helps) until primality is reached.

As actually proving primality may take way too much computing power, it will be enough for the second part to pass a "probable prime" test (e.g. Miller-Rabin) to a probability of less than 2<sup>-100</sup>.

The person with the smallest probable prime wins.

# Answer
## Java (about 2048 bits)

```
14951059135011030015480908520726485619103063818476057564660360628799292628035097139943806440612109515246411930476451010075357954683100898936593739762786721583164361680031433048702186473094092210118641364347032899100220949873928633438856732508590863996147513646363328498023218161000104939462296626885931085914071985322044175133733909287366858309877885352980365735019082872958155754848273583139151810812417879417661663044291630490856568568829579704849173609110647303708828534149066778229242936297219753177569833591637704406031011600073082097633261877649625598598670707453831253888534424016277678136396605413799234576729

```

The code is

```
void C(int[]s,int[]k){int a=k[0]^s[84]|256,b=k[1]^s[85],c=k[2]^k[3]<<8^k[4]<<16^s[86]^s[87]<<8^s[88]<<16,d=c&7,e=0,f,i=127;for(c=c*2+8-d;++i<2048;e>>=8){e+=S[f=(c>>17^c>>14^c>>13^c>>5)&255]+T[d=Q[b]^R[a]];b=a/2;a=a&1<<8^d;c=c<<8|f;s[i]=P[s[i]]^e&255;}}//!Y

```

I took the liberty of renaming the lookup tables from `CSSt1` ... `CSSt5` to `P` ... `T`, and the method from `CSSDescramble` to `C`. I also ditched the gzip step, because it was giving a larger file than the source.
> 4 votes

---
Tags: code-challenge, primes, compression, encryption
---


title: Immutable dictionaries in Haskell

text:
# Question
Title: Immutable dictionaries in Haskell
You need to implement immutable dictionaries using only functions without any other data types (custom or built-in). The dictionary must be indexed by any data type of class Eq and contain values of arbitrary type, but all the values in a dictionary should be of the same type.

Here are some examples of usage:

```
dict `access` True -- returns value of key True
dict `access` "y"  -- returns value of key "y"
(update "x" 10 dict) `access` "x" -- returns 10 for any dict

```

# Answer
> 3 votes
```
update key1 value obj = \key2 -> if key2 == key1 then value else obj key2
access = id

```

Given the above definitions, your examples should work. Also, you can define an empty dictionary as `const x` where `x` is the default value for keys not in the dictionary.

---
Tags: code-golf, data-structures, haskell
---


title: Optimally solve the Flux Puzzle

text:
# Question
Title: Optimally solve the Flux Puzzle
Flux is very similar to the Fifteen Puzzle.

However, instead of numbers, the squares are colors.

* There are 4 colors: Red, Yellow, Blue, and Gray.
    + There are *exactly* 4 red squares, 4 yellow squares, 2 blue squares, 1 gray square, and 1 empty square.
* The grid has 3 rows and 4 columns
* A grid configuration is **solved** when the **top row** is exactly the same as the **bottom row**.
* The middle row is *not relevant* when considering whether the board is solved.
* You do not have to handle invalid input. Trust that there will be the correct number of each of the input symbols.

## Input

* You must accept an input of twelve of these characters that use these symbols to represent a square on the board:
    + `RYGB_`
* These input characters **must** be interpreted to go across, then down.
* It is your choice whether you require some other character (newline, EOF, whatever) to terminate input, or just go as soon as you've received 12 characters.

Example:

```
YRGYB_BRRYYR

```

which corresponds to to the board:

```
YRGY
B_BR
RYYR

```

## Output

* You must output the moves required for an **OPTIMAL** solution
* These will use the characters `LRUD` for Left, Right, Up, Down. This is considered to be the "piece moves to the left", **not** the "emptiness moves to the left"

Example:

```
LURDRDLULDLU

```

And then print out the resulting board. For the example we've used so far:

```
RBYR
YYG_
RBYR

```

## Other rules

* Your program must run in under 15 seconds or it is disqualified.
    + Make sure to try it with the following board: `RRRRBG_BYYYY`
    + That board, with it's three symmetries, is the "hardest" possible board.
* You may not use any external resources, or have any input data files.

## Some stats

* There are exactly 415,800 possible boards
* There are exactly 360 "solution" boards
* My program that I wrote to test this out runs in about 2 seconds in Java, without much optimization.
    + This program, with minimal golfing, is 1364 bytes.

## Scoring

* This is code-golf, fewest characters that meets the other requirements wins!

# Answer
> 2 votes
# Smalltalk 497

```
|b R M s g a|
b:=Stdin nextLine.R:='D--R-L--U'.
M:=#((6 9)(4 6 9)(4 6 9)(4 9)(1 6 9)(1 4 6 9)(1 4 6 9)(1 4 9)(6 1)(4 6 1)(4 6 1)(4 1)).
s:=Set new.q:=OrderedCollection new.
a:=[:p :m|(s includes:p)ifFalse:[s add:p.q add:p->m]].
a value:b value:''.
[|x i n p|
x:=q removeFirst.p:=x key.i:=(p indexOf:$_).
(M at:i)do:[:m||v|
n:=p copy.n at:i put:(p at:i+m-5);at:i+m-5put:$_.
v:=(x value,(R at:m)).
(n to:4)=(n from:9)ifTrue:[
v printCR.(n splitForSize:4)map:#printCR.^self].
a value:n value:v]]loop.

```

Input:

```
YRGYB_BRRYYR

```

Output:

```
DLURRULDDLLU
YBYR
RGR_
YBYR

```

Exec. Time (bytecode, not jitted): 100ms

Input:

```
RRRRBG_BYYYY

```

Output:

```
DRRUULLDLURDDRRULULD
YBRR
GY_Y
YBRR

```

Exec. Time 2s unjitted; 0.8s jitted (most time spent in collection code)

Here is an ungolfed version for readability:

```
|b R M s g add|
b:=Stdin nextLine.
R:='D--R-L--U'.
M:=#((6 9)(4 6 9)(4 6 9)(4 9)
     (1 6 9)(1 4 6 9)(1 4 6 9)(1 4 9)
     (6 1)(4 6 1)(4 6 1)(4 1)).
s := Set new.
queue := OrderedCollection new.

add := [:p :m |
  (s includes:p) ifFalse:[
    s add:p.
    queue add:(p->m).
  ]].

add value:b value:''.

[
  |x i n p|

  x := queue removeFirst.
  p := x key.
  i := (p indexOf:$_).
  (M at:i) do:[:m |
    |v|
    n := p copy.
    n at:i put:(p at:i+m-5); at:i+m-5 put:$_.
    v:=(x value,(R at:m)).
    (n to:4)=(n from:9) ifTrue:[
      v printCR.
      (n splitForSize:4) map:#printCR.
      ^ self
    ].
    add value:n value:v]
] loop.

```

# Answer
> 0 votes
# Python 372

This was longer than I expected, I might go back later and see if I can optimize more. It uses a pretty inefficient method of brute-forcing the answer, but it seems to consistently run at no more than 8 seconds on my relatively old laptop.

```
A=lambda s,i,n:s[:i]+n+s[i+1:]
def M(b):
 i=b.find('_')
 for d,n in([('L',i+1)]if i%4<3 else[])+([('R',i-1)]if i%4>0 else[])+([('D',i-4)]if i>4 else[])+([('U',i+4)]if i<8 else[]):yield d,A(A(b,i,b[n]),n,'_')
def F():
 c=[('',raw_input())]
 while 1:
    for (m,b)in c:
     if b[:4]==b[8:]:return m,b
    c=[(m+d,n)for(m,b)in c for(d,n)in M(b)]
print F()

```

# Answer
> 0 votes
# Java 1364

I golfed this some but I'm sure there's plenty more I could do. For example I close the input stream which is not necessary ;) I just wanted to put **something** up.

```
import java.util.*;class F{enum D{R{B b(B i){return i.z==3?null:g(i,1);}},L{B b(B i){return i.z==0?null:g(i,-1);}},D{B b(B i){return i.y==2?null:g(i,4);}},U{B b(B i){return i.y==0?null:g(i,-4);}};abstract B b(B i);B g(B i,int f){f+=4*i.y+i.z;char[]s=i.s.toCharArray();s[i.e]=s[f];s[f]='_';return w.get(new String(s));}}enum C{_,G,B,R,Y;}class B{C[][]a=new C[3][4];String s;int y,z,e,c;B p;D d;B(String p){int i,j,q;for(i=0;i<3;i++){for(j=0;j<4;j++){q=4*i+j;a[i][j]=C.valueOf(p.substring(q,q+1));if(a[i][j]==C._){y=i;z=j;e=q;}}}s=p;}boolean v(){return Arrays.equals(a[0],a[2]);}void p(B b,D n){p=b;d=n;c=p.c+1;}String g(){String u="\n";for(int i=0;i<3;i++,u+="\n")for(int j=0;j<4;j++)u+=a[i][j];return u;}}Set<B>b=new HashSet<B>(),p;static Map<String,B>w=new HashMap<>();void p(String f,String s){int n=s.length();if(n==0){B o=new B(f);w.put(f,o);if(o.v())b.add(o);}else{Set e=new HashSet();for(int i=0;i<n;i++){char c=s.charAt(i);if(!e.contains(c)){p(f+c,s.substring(0,i)+s.substring(i+1,n));e.add(c);}}}}public static void main(String[]a){new F().r();}void r(){Scanner c=new Scanner(System.in);String t=c.nextLine();p("",t);for(int i=0;i<20;i++,b=p){p=new HashSet<>(b);for(B o:b)if(o.c==i)for(D d:D.values()){B n=d.b(o);if(n!=null&&!p.contains(n)){n.p(o,d);p.add(n);}}}B q=w.get(t);while(!q.v()){System.out.print(q.d);q=q.p;}System.out.println(q.g());c.close();}}

```

Ungolfed:

```
import java.util.*;

class F {
    enum D {
        R {
            B b(B i) {
                return i.z == 3 ? null : g(i, 1);
            }
        },
        L {
            B b(B i) {
                return i.z == 0 ? null : g(i, -1);
            }
        },
        D {
            B b(B i) {
                return i.y == 2 ? null : g(i, 4);
            }
        },
        U {
            B b(B i) {
                return i.y == 0 ? null : g(i, -4);
            }
        };

        abstract B b(B i);

        B g(B i, int f) {
            f += 4*i.y + i.z;
            char[] s = i.s.toCharArray();
            s[i.e] = s[f];
            s[f] = '_';

            return w.get(new String(s));
        }
    }

    enum C {
        _, G, B, R, Y;
    }

    class B {
        C[][] a = new C[3][4];
        String s;

        int y,z,e,c;

        B p;
        D d;

        B(String p) {
            int i,j,q;
            for(i = 0; i < 3; i++) {
                for(j = 0; j < 4; j++) {
                    q=4*i+j;
                    a[i][j] = C.valueOf(p.substring(q,q+1));
                    if(a[i][j] == C._) {
                        y = i;
                        z = j;
                        e = q;
                    }
                }
            }

            s = p;
        }

        boolean v() {
            return Arrays.equals(a[0], a[2]);
        }

        void p(B b, D n) {
            p = b;
            d = n;
            c = p.c + 1;
        }

        String g() {
            String u = "\n";
            for(int i = 0; i < 3; i++,u+="\n")for(int j = 0; j < 4; j++) u += a[i][j];
            return u;
        }
    }

    Set<B> b = new HashSet<B>(),p;
    static Map<String, B> w = new HashMap<>();

    void p(String f, String s) {
        int n = s.length();
        if (n == 0) {
            B o = new B(f);
            w.put(f, o);
            if(o.v()) b.add(o);
        }
        else {
            Set e = new HashSet();
            for (int i = 0; i < n; i++) {
                char c = s.charAt(i);
                if(!e.contains(c)) {
                    p(f + c, s.substring(0, i) + s.substring(i+1, n));
                    e.add(c);
                }
            }
        }
    }

    public static void main(String[] a) {
        new F().r();
    }

    void r() {
        Scanner c = new Scanner(System.in);
        String t = c.nextLine();

        p("", t);

        for(int i = 0; i < 20; i++, b=p) {
            p = new HashSet<>(b);

            for(B o : b)
                if(o.c == i)
                    for(D d : D.values()) {
                        B n = d.b(o);
                        if(n != null && !p.contains(n)) {
                            n.p(o, d);
                            p.add(n);
                        }
                    }
        }

        B q = w.get(t);
        while(!q.v()) {
            System.out.print(q.d);
            q = q.p;
        }
        System.out.println(q.g());

        c.close();
    }
}

```

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


# Question
Title: Program that permutes itself to encode a string (quine-variant)
Write a program that prints the following 80-character line:

> This program from codegolf.stackexchange.com permutes itself to encode a string.

then accepts one line of input, then prints its source code with its code points possibly reordered (none added and none deleted). When that code is executed, the same has to happen, except the printed line would be the most recent line of input.

The Perl-style regex `^[A-Za-z0-9. ]{80}$` will match any line of input. You cannot make any additional assumption.

A submission's score is the number of **code points** in its source code **less 94**. Lower is better.

The code must not do anything that would be unacceptable in a quine (*e.g.* file reading). In particular, any submission with a negative score must be cheating somehow, as 93! is less than 6480.

**Added 2014-04-21:** Your program's entire source code must be well-formed in the character encoding under which you count code points. For example, you cannot use 80 consecutive bytes in the UTF-8 trailing byte range (80..BF) and count each as a single U+FFFD REPLACEMENT CHARACTER (or worse, as not a code point at all).

Additionally, if the encoding allows multiple ways to encode a code point (*e.g.* SCSU), your program, as well as all programs it directly or indirectly generates, must only use one of them (or at least all must be treated equivalently throughout the code).

# Answer
# GolfScript, ~~231~~ ~~162~~ 131

```
'1àâ4ÿaVo5GùpZBtiXOürsóNîMmWåKHc09JdñúêyzíECäYïhDU ãáIFõ6é8òRìjTv23ønuðLwxfSkôbëAelqý.çèPQ
öûg7'{0@.$[{}/]:&\{@2$,*2$2$?+@@^}/{;65base}:b~{&=}%''+puts'"#{`head -1`}"'~{&?}%)b[94,{)1$1$%@@/}/;]-1%&\[{1$=.@^}/]"'".@+\+\'.~'}.~

```

### How it works

We start by choosing 94 different characters that will get permuted to encode a string. Any 94 characters would work, but we choose the following for golfing purposes:

```
\n .0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
àáâãäåçèéêëìíîïðñòóôõöøùúûüýÿ

```

Let's call the array of these characters “&”.

The line of input will always contain 81 characters (including the LF). All of those characters are present in the first 65 characters of “&”. This is the sole reason for choosing characters in the upper 128 bytes.

We replace each character of the string by its index in “&”, so LF becomes 0, space becomes 1, etc.

We consider the 81 obtained numbers the digits of a single base 65 number. Let's call this number “N”.

Now, we enumerate all possible permutations of “&” and retrieve the permutation corresponding to the number from above. This is achieved in the following manner:

1. Set `c = 1` and `A = []`.
2. Prepend `N % c` to `A`.
3. Set `N = N / c` and `c = c + 1`.
4. If `c < 95`, go back to 2.
5. Set `i = 0` and `s = ""`.
6. Retrieve the charcter `&[A[i]]`, append it to “s” and remove it from “&”.
7. Set `i = i + 1`.
8. If `i < 94` go back to 6.

Suppose we have code blocks “E” and “D” that encode and decode a string as explained above.

Now, we need a wrapper for those code blocks that complies with the requirements of the question:

```
'encoded string'{\.$[{}/]:&; D puts '"#{`head -1`}"'~ E "'".@+\+\'.~'}.~

```

This does the following:

* `{…}.~` defines a block, duplicates it and executes the second copy. The first copy will remain on the stack.
* `\.$` swaps the encoded string with the block and creates a copy of the encoded string, with sorted characters.
* `[{}/]:&;` converts the string from above into an array, saves it in “&” and discards it.
* `D puts` decodes the encoded string and prints the result.
* `'"#{`head -1`}"'~` reads one line of input by executing `head -1` in the shell.
* `E "'".@+\+` encodes the string and prepends and appends a single quote.
* `\'.~'` swaps the encoded string and the block and appends the string `'.~'`.
* After the block has been executed, GolfScript prints the contents of the stack (encoded string, block, `'.~'`) and exits.

“E” can be defined as follows:

```
{&?}%        # Replace each character by its index in “&”.
);           # Remove the last integer from the array, since it corresponds to the LF.
65base       # Convert the array to an integer “N” by considering it a base 65 number.
[            #
  94,        # For each integer “c” in 0 … 93:
  {          #
    )        # Increment “c”.
    1$1$%    # Push “N % c”.
    @@/      # Rotate “N % c” below “N” and “c” and divide the first by the latter.
  }/;        # Discard “N”.
]            # Collect the results of “N % c” in an array “A”.
-1%          # Reverse “A”.
&\           # Push “&” and swap it with “A”.
[            #
  {          # For each “j” in “A”:
    1$=.[]+  # Push “&[j] [&[j]]”.
    @^       # Rotate “&” on top of “[&[j]]” and take their symmetric difference.
  }/         #
]            # Collect the charcters into an array.

```

“D” can be defined as follows:

```
0&           # Push 0 (initial value of the accumulator “A”) and “&”.
@            # Rotate the encoded string on top of “&”.
{            # For each character “c” of the encoded string:
    @2$,*    # Rotate “A” on top of the stack and multiply it by the length of “&”.
    2$2$?+   # Get the index of “c” in “&” and add it to “A”.
    @@^      # Rotate “A” below “&” and “c” and take their symmetric difference.
}/;          # Discard “&”.
65base       # Convert “A” into the array of its digits in base 65.
{&=}%        # Replace each digit by the corresponding character in “&”.
''+          # Convert the resulting array into a string.

```

Final golfing:

* Replace `\.$[{}/]:&;0&@` with `0@.$[{}/]:&\` to save two characters.
* Define the function `{;65base}:b` to save one character.
* Remove all whitespace except the trailing LF and the LF in the string.

### Example

```
$ # Create GolfScript file using base64 to avoid encoding issues.
$ base64 > permute.gs -d <<< JzHg4jT/YVZvNUf5cFpCdGlYT/xyc/NO7k1tV+VLSGMwOUpk8frqeXrtRUPkWe9oRFUg4+FJRvU26TjyUuxqVHYyM/hudfBMd3hmU2v0YutBZWxx/S7n6FBRCvb7ZzcnezBALiRbe30vXTomXHtAMiQsKjIkMiQ/K0BAXn0vezs2NWJhc2V9OmJ+eyY9fSUnJytwdXRzJyIje2BoZWFkIC0xYH0iJ357Jj99JSliWzk0LHspMSQxJCVAQC99LztdLTElJlxbezEkPS5AXn0vXSInIi5AK1wrXCcufid9Ln4K
$
$ # Set locale to en_US (or any other where one character is one byte).
$ LANG=en_US
$
$ # Go back and forth between two different strings.
$ # Second and sixth line are user input, not output from the script.
$
$ golfscript permute.gs | tee >(tail -n+2 > tmp.gs) && golfscript tmp.gs && rm tmp.gs
This program from codegolf.stackexchange.com permutes itself to encode a string.
Permuting source code code points to encode a string is a certain quine variant.
'18äJoS3sgV9qdçëxm0ÿKMNe5íPî.Htn2ciâIuøbRZéð4AwB7áìUüöôWõèûfñåLàóDrhQlO6
pTaýzòkùYCyFêïãG júEvX'{0@.$[{}/]:&\{@2$,*2$2$?+@@^}/{;65base}:b~{&=}%''+puts'"#{`head -1`}"'~{&?}%)b[94,{)1$1$%@@/}/;]-1%&\[{1$=.@^}/]"'".@+\+\'.~'}.~
Permuting source code code points to encode a string is a certain quine variant.
This program from codegolf.stackexchange.com permutes itself to encode a string.
'1àâ4ÿaVo5GùpZBtiXOürsóNîMmWåKHc09JdñúêyzíECäYïhDU ãáIFõ6é8òRìjTv23ønuðLwxfSkôbëAelqý.çèPQ
öûg7'{0@.$[{}/]:&\{@2$,*2$2$?+@@^}/{;65base}:b~{&=}%''+puts'"#{`head -1`}"'~{&?}%)b[94,{)1$1$%@@/}/;]-1%&\[{1$=.@^}/]"'".@+\+\'.~'}.~
$
$ # Sort all characters from the original source code and hash them.
$ fold -1 permute.gs | sort | md5sum
b5d978c81df5354fcda8662cf89a9784  -
$
$ # Sort all characters from the second output (modified source code) and hash them.
$ golfscript permute.gs | tail -n+2 | fold -1 | sort | md5sum
Permuting source code code points to encode a string is a certain quine variant.
b5d978c81df5354fcda8662cf89a9784  -
$
$ # The hashes match, so the characters of the modified source code are a permutation
$ # of the character of the original one.

```
> 6 votes

# Answer
# Perl, ~~1428~~ 1099

This has 1193 ASCII characters (including 960 permuted binary digits). 1193 - 94 = **1099**

```
$s='010011100001100010101100111111101001101011101000100000101011011010100110111111011111101011101000100110111111011100101000011101011110100000101000100101011111111110101100101101011010011100100100011110110001011100100001011010100111100000011110111110011100101000100110111111101001011110101011100110101110101101011110101100111111100010101101101100011110100101011111111111101101101000111111011110100111011100101000011101011110111111011010111111101100101101101011100010100111100000111110';$_=q{$i=join'',A..Z,a..z,0..9,'. ';print map({substr$i,oct'0b'.$_,1}$s=~/.{6}/g),$/;chop($s=<>);$s=join'',map{sprintf"%06b",index$i,$_}$s=~/./g;$t=join'',map{$_ x(480-(()=$s=~/$_/g))}0,1;print"\$s='$s';\$_=q{$_};eval#$t"};eval#000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

```

## My first design

Before I took a suggestion from Dennis to switch to binary, my program permuted octal digits.

My first design encodes each string in 160 octal digits, with 2 digits per character. This encoding has 1008=64 different characters. The octal system has 8 different digits. The program must have 160 copies of each digit, so it permutes 8×160=1280 digits.

I keep 160 digits in `$s` and the other 1120 digits in `$t`. I start with a program that is not a quine, but only prints the assignments to `$s` and `$t` for the next run. This is it:

```
$s = '2341425477515350405332467737535046773450353640504537765455323444366134413247403676345046775136534656553654774255543645377755507736473450353677327754555342474076';
$t = '0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222223333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333334444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666667777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777';

# $i = character map of 64 characters, such that:
#  substr($i, $_, 1) is the character at index $_
#  index($i, $_) is the index of character $_
$i = join '', 'A'..'Z', 'a'..'z', '0'..'9', '. ';

# Decode $s from octal, print.
#  1. ($s =~ /../g) splits $s into a list of pairs of octal digits.
#  2. map() takes each $_ from this list.
#  3. oct() converts $_ from an octal string to a number.
#  4. substr() on $i converts number to character.
#  5. print() outputs the characters from map() and a final "\n".
print map({ substr $i, oct, 1 } $s =~ /../g), "\n";

# Read new $s, encode to octal.
#  1. ($s = <>) reads a line.
#  2. chop($s) removes the last character of $s, the "\n".
#  3. ($s =~ /./g) splits $s into characters.
#  4. map() encodes each character $_ as a pair of octal digits.
#  5. join() concatenates the pairs from map().
chop($s = <>);
$s = join '', map { sprintf "%02o", index $i, $_ } $s =~ /./g;

# Make new $t.
#  1. map() takes each $_ from 0 to 7.
#  2. $_ x (160 - (() = $s =~ /$_/g)) makes a string where $_ repeats
#     160 times, minus the number of times that $_ appears in $s.
#  3. join() concatentates the strings from map().
$t = join '', map { $_ x (160 - (() = $s =~ /$_/g)) } 0..7;

# Print the new assignments for $s and $t.  This is not yet a quine,
# because it does not print the rest of the program.
print "\$s = '$s';\n\$t = '$t';\n";

```

`(() = $s =~ /$_/g))` is an assignment to an empty list of variables. I take this trick from the context tutorial at PerlMonks. It forces list context on the match operator `=~`. In scalar context, the match would be true or false, and I would need a loop like `$i++ while ($s =~ /$_/g)` to count the matches. In list context, `$s =~ /$_/g` is a list of matches. I put this list in the scalar context of a subtraction, so Perl counts the list elements.

To make a quine, I take the form `$_=q{print"\$_=q{$_};eval"};eval` from the Perl quines at Rosetta Code. This one assigns a string `q{...}` to `$_` and then calls `eval`, so I can have my code in a string and also run it. My program becomes a quine when I wrap my third to last lines in `$_=q{` and `};eval`, and change my last `print` to `print "\$s = '$s';\n\$t = '$t';\n\$_=q{$_};eval"`.

Finally, I golf my program by changing the first assignment to `$t` to a comment, and by removing extra characters.

This has 1522 ASCII characters (including 1280 permuted octal digits).
1522 - 94 = **1428**

```
$s='2341425477515350405332467737535046773450353640504537765455323444366134413247403676345046775136534656553654774255543645377755507736473450353677327754555342474076';#0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222223333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333334444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666667777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777
$_=q{$i=join'','A'..'Z','a'..'z','0'..'9','. ';print map({substr$i,oct,1}$s=~/../g),"\n";chop($s=<>);$s=join'',map{sprintf"%02o",index$i,$_}$s=~/./g;$t=join'',map{$_ x(160-(()=$s=~/$_/g))}0..7;print"\$s='$s';#$t\n\$_=q{$_};eval"};eval

```

## The switch to binary

In the comments, Dennis noticed that 960 permuted binary digits would be fewer than 1280 octal digits. So I graphed the number of permuted digits for each base from 2 to 16.

```
Maxima 5.29.1 http://maxima.sourceforge.net
using Lisp ECL 13.5.1
...
(%i36) n : floor(x);
(%o36)                             floor(x)
...
(%i41) plot2d(n * ceiling(log(64) / log(n)) * 80, [x, 2, 16],
              [xlabel, "base"], [ylabel, "number of permuted digits"]);
(%o41)

```

Though base 8 is a local minimum, bases 2 and 3 and 4 tie for best base, at 960 permuted digits. For code golf, base 2 is best because Perl has conversions for base 2.

Replacing 1280 octal digits with 960 binary digits saves 320 characters.

Switching code from octal to binary costs 8 characters:

* Change `oct` to `oct'0b'.$_` costs 7.
* Change `/../g` to `/.{6}/g` costs 2.
* Change `"%02o"` to "%06b"\` costs 0.
* Change `160` to `480` costs 0.
* Change `0..7` to `0,1` saves 1.

I learned some Perl golf tips. They save 14 characters:

* Change `'A'..'Z','a'..'z','0'..'9'` to `A..Z,a..z,0..9`, using barewords and bare numbers, saves 12 characters.
* Change `"\n"` to `$/` saves 2 characters.

I save 3 characters by moving the `#$t` comment to the end of the file. This removes the newline that ends the comment, and a literal `\n` in the quine.

These changes save a total of 329 characters, and reduce my score from 1428 to 1099.
> 2 votes

---
Tags: code-golf, quine
---