title: Word guessing game

text:
# Question
Title: Word guessing game
A program should take an input on stdin, and guess what a word might be. It should run as a session. One example session is shown below. Characters are fed to it, with a * for a letter not revealed; it should remember letters already revealed. It shows possible words in a list if the total number words found is less than 20, otherwise it shows the count of words.

I recommend `/usr/share/dict/words` on any Linux/Unix for the list of words, or your favourite word list on other platforms.

**Example session (yours may vary):**

```
>>> *****
6697 matches
>>> G****
312 matches
>>> *u***
Trying Gu***
35 matches
>>> Gu**s
Gus's
Guy's
guess
gulfs
gulls
gulps
gum's
gun's
gurus
gusts
gut's
guy's
12 matches
>>> **e**
Trying Gue*s
Is it "guess"?

```

# Answer
> 3 votes
## Bash (171)

```
#!/bin/bash
s=`cat /dev/stdin | sed 's/\*/\./g'`;o=`cat /usr/share/dict/words | grep -x $s`;w=`echo "$o" | wc -l`;if [ $w -lt '20' ]; then echo "$o";fi;echo "$w match(es)"

```

# Answer
> 2 votes
## Perl, 170 chars

```
open W,'</usr/share/dict/words';@D=<W>;
while(<>){@W=split//,$w;$w&&s/\*/$W[$-[0]]/ge;y/*/./;$w=$_;
($r=@R=grep/^$w$/i,@D)<20&&map{print}@R;print$r." matches\n";$r<2&&last}

```

Added (not counted) newlines for clarity.

# Answer
> 0 votes
## PHP, 302

```
<?system('stty -icanon');$i=0;$s=explode(PHP_EOL,file_get_contents('/usr/share/dict/words'));while(1){$q.=fread(STDIN,1);system('clear');$x=0;$a='';$i++;for($j=0;$j<count($s);$j++){if(!strncasecmp($q,$s[$j],$i)){$x++;$a.="\n$s[$j]";}}echo str_pad($q,20,'*');echo$x<=20?"\n$a":'';echo"\n$x matches\n";}

```

---
Tags: code-golf, word, search
---


# Question
Title: Code Golf: What is the spaceship's fate? [floating point version]
This question is slightly harder than the ASCII art version. There is no art, and now you get to do some floating point arithmetic!

# The Challenge

The U.S.S. StackExchange was traveling through the gravity field of planet cg-00DLEF when an astronomical explosion occurred on board. As the head programming officer of the ship, it is your job to simulate the trajectory of your ship in order to predict whether you will be forced to crash land in cg-00DELF's solar system. During the explosion, your ship was heavily damaged. Due to the limited free DEEEPRAROM\* of the spaceship, you must write your program in as few characters as possible.

\*Dynamically Executable Electronically Erasable Programmable Random Access Read Only Memory

# The Simulation

Somewhat like the ASCII art version, there will be the idea of time-steps. In the other version, a time-step was a relatively large amount of time: the ship could travel way beyond the gravity of a planet in a single time-step. Here, the time-step is a much smaller unit of time due to the larger distances involved. One major difference, however, is the non-existence of cells. The spaceship's current location and velocity will be floating point numbers, along with the gravitational forces involved. Another change is the fact that planets now have a much larger size.

There will be up to three planets in the simulation. All three will have a specific location, radius, and gravity. The gravity for each planet is a vector that exerts a force directly towards the center of the planet. The formula to find the strength of this vector is `(Gravity)/(Distance**2)`, where the distance is the exact distance from the ship to the center of the planet. This means that there is no limit to where gravity can reach.

At any specific time, the spaceship has a velocity, which is the distance and angle that it traveled from last time-step to now. The ship also has momentum. The distance that it will travel between the current time-step and the next is the sum of its current velocity added to all of the gravity vectors at its location. This becomes the spaceship's new velocity.

Each simulation has a time limit of 10000 time steps. If the spaceship travels inside of a planet (it is closer to the center of the planet than the planet's radius), then it crashes into that planet. If the spaceship does not crash into any planet by the end of the simulation, then it is presumed to have escaped from gravity. It is unlikely that the ship could be aligned so perfectly that it manages to stay in orbit for 10000 time-steps while crashing on the 10001st time-step.

# Input

Input will be four lines to STDIN. Each line consists of four comma-delimited numbers. Here is the format of the numbers:

```
ShipLocX,ShipLocY,ShipVelX,ShipVelY
Planet1LocX,Planet1LocY,Planet1Gravity,Planet1Radius
Planet2LocX,Planet2LocY,Planet2Gravity,Planet2Radius
Planet3LocX,Planet3LocY,Planet3Gravity,Planet3Radius

```

If there are fewer than three planets, then the leftover lines will be filled with zeros for all values. Here is an example input:

```
60,0,0,10
0,0,4000,50
100,100,4000,50
0,0,0,0

```

This means that the spaceship is located at (60,0) and is traveling straight "up/north" at a rate of 10 units/time-step. There are two planets, one located at (0,0) and one at (100,100). Both have a gravity of 4000 and a radius of 50. Even though all of these are integers, they will not always be integers.

# Output

Output will be a single word to STDOUT to tell whether the spaceship has crash landed or not. If the ship crash lands, print `crash`. Otherwise, print `escape`. Here is the expected output for the above input:

```
crash

```

You may be wondering what happened. Here is a Pastebin post that has a detailed flight log for the spaceship. Numbers aren't very good at helping people visualize the event so here is what happened: The spaceship manages to escape the gravity of the first planet (to its west) with the help of the gravity of the second planet (to its northeast). It moves north and then passes slightly to the west of the second planet, barely missing it. It then curves around the northern side of the planet and crashes into the eastern side of the second planet.

# Some more cases for examination

```
60,0,10,-10
0,0,2000,50
100,100,1357.9,47.5
0,0,0,0

```

escape (due to the inverse square law, 2000 isn't much gravity if you are 60 units away)

```
0,0,0,0
100,100,20000,140
-50,-50,50,50
-100,-100,50,50

```

crash (the first planet is extremely massive and extremely close)

```
0,0,0,0
0,0,0,0
0,0,0,0
0,0,0,0

```

escape (this is an edge case: there are no planets and a straightforward interpretation would suggest that the spaceship is directly on top of the planets)

# Rules, Restrictions, and Notes

This is code golf. Standard code golf rules apply. Your program should be written in printable ASCII characters only. You cannot access any sort of external database. You may write entries in any language (other than one that is specialized towards solving this challenge).

End Transmission

# Answer
> 6 votes
## Python, 178 170 chars

```
p=input
a,b,c,d=p()
x=a+b*1j
v=c+d*1j
P=(p(),p(),p())
R='escape'
for i in' '*10000:
 for a,b,g,r in P:
  d=a+b*1j-x;v+=g*d/abs(d)**3
  if abs(d)<r:R='crash'
 x+=v
print R

```

# Answer
> 2 votes
## Golfrun/GolfScript?, ~~243~~ 232 chars

```
10000:M;n%(','%2/{{~}%}/{{M*}%}:_~:v;_:x;'escape':R;{[','%2/{{~M*}%}/]}%:P;
M,{;P{~\x{0\-}%{+~@+@@+[\]}:|~:d.[~0\-]{[+.2%~*\.-2%~*@\-\.3%~*\(;);~*+]}:&~);~sqrt:z
..**\~d@[`~0]\&@M.*/\{1$/}%v|:v;;z\<{'crash':R;}{}if}/x v|:x;}/R puts

```

Golfrun is a language I'm working on, born as GolfScript C interpreter, but soon drifted away someway; though I've written this code without using knowingly specific Golfrun features (except for `sqrt`), the test with the original GolfScript failed (I had to add the sqrt feature to the original code, I am not a Ruby guru but I believe the problem is not my tweaking).

The first problem with this solution is that Golfrun, as GolfScript, has no floating point math. It is "simulated" magnifying the numbers, hopefully in the correct way (but I am not 100% confident I've done it coherently). Even so, the solution does not handle floating point numbers as input, so I had to magnify them by hand to have only integer numbers.

Trying to implement the algorithm in the Python code, I have also implemented bits of complex math in a rather "general" way. Manipulating the algorithm in order to avoid this, and/or inlining whenever possible, delaying the definitions, could save other chars...

How do I know this code works? Indeed, I am not sure it does! But giving the examples as input (after "removing" points where they appear), it wrote the expected results, except for the "corner case" (which raises an exception in Python too)...

---
Tags: code-golf, math, printable-ascii, simulation
---


title: Pretty-printing polynomials

text:
# Question
Title: Pretty-printing polynomials
A polynomial over a variable *x* is a function of the form

> p(x) = anxn \+ an-1xn-1 \+ ... + a1x + a0

where *a0 ... an* are the *coefficients*. In the simplest case, the coefficients are integers, e.g.

> p1(x) = 3x2 \+ 4x + 1

By allowing the coefficients to be polynomials over another variable, we can define polynomials over multiple variables. For example, here is a polynomial over *x* whose coefficients are polynomials over *y* with integer coefficients.

> p2(x,y) = (2y + 1)x2 \+ (3y2 \- 5y + 1)x + (-4y + 7)

However, we often prefer to write these fully expanded as

> p2(x,y) = 2x2y + x2 \+ 3xy2 \- 5xy + x - 4y + 7

Your task is to write a program that will pretty-print a given polynomial in this format.

### Input

Your program will receive a single line on standard input* describing a polynomial over multiple variables in the following format.

```
<name> <variables> <coefficients>

```
* `<name>` is one or more arbitrary non-whitespace characters.
* `<variables>` is one or more characters between `a` and `z` inclusive, each representing a variable. There are no duplicates, but note that the order is significant, as it affects how the terms should be ordered in the output.
* `<coefficients>` is one or more coefficients, separated by spaces, in order of increasing degree.

Each coefficient is either an integer in the usual base 10 notation, or another list of coefficients between square brackets. The different variables correspond to the nesting level of the coefficients, with the "outermost" list corresponding to the first variable and so on. The number of nesting levels will never exceed the number of variables.

For example, the polynomials *p1* and *p2* above can be represented as follows.

```
p1 x 1 4 3
p2 xy [7 -4] [1 -5 3] [1 2]

```

Since constant polynomials can be interpreted as polynomials over any set of variables, some polynomials may be written in multiple ways. For example, the coefficients of *p3(x,y,z) = 4* can be written as `4`, `[4]` or `[[4]]`.

### Output

Your program should pretty-print the input polynomial on standard output* in the following format.

```
<name>(<variables>) = <terms>

```
* `<name>` is the name of the polynomial as received.
* `<variables>` is the list of variables in the order received, interspersed with commas.
* `<terms>` are the terms of the fully expanded polynomial, formatted according to the rules below.
* Each term is an integer coefficient followed by powers of each variable in the order defined in the input, all separated by a single space. The general format is `<variable>^<exponent>`.
* The terms are sorted by the exponents of the variables in decreasing lexicographical order. For example, `3 x^2 y^4 z^3` should come before `9 x^2 y z^13` because `2 4 3 > 2 1 13` lexicographically.
* Omit terms where the integer coefficient is zero, unless the whole polynomial is zero.
* Omit the integer coefficient if its absolute value is one, i.e. write `x` instead of `1 x`, unless this is a constant term.
* When the exponent of a variable in a term is zero, omit the variable from that term.
* Similarly, when the exponent of a variable is one, omit the exponent.
* The terms should be separated by `+` or `-` signs, with a space on each side, according to the sign of the integer coefficient. Similarly, include the sign in front of the first term if it's negative.

### Examples

```
Input                             Output
================================  =======================================================
p1 x 1 4 3                        p1(x) = 3 x^2 + 4 x + 1
p2 xy [7 -4] [1 -5 3] [1 2]       p2(x,y) = 2 x^2 y + x^2 + 3 x y^2 - 5 x y + x - 4 y + 7
p3 xyz [4]                        p3(x,y,z) = 4
foo bar [0 2 [0 1]] [[3] [5 -1]]  foo(b,a,r) = - b a r + 5 b a + 3 b + a^2 r + 2 a
quux y 0 0 0 0 0 1337             quux(y) = 1337 y^5
cheese xyz [[0 1]]                cheese(x,y,z) = z
zero x 0                          zero(x) = 0

```

### Winning criteria

This is code golf. The shortest program wins. Standard code golf rules apply.

### Bonus challenge

Write another program which does the reverse operation, i.e. takes the pretty-printed output of your original program and gives you back one of the possible corresponding inputs. This is purely for bragging rights and has no effect on your score.

* If your chosen programming language doesn't support standard input/output, you may specify how I/O is handled.

# Answer
> 2 votes
Mathematica:

```
Expand[Input[]] // TraditionalForm

```

will produce the expanded form.

Example input:

```
(2y + 1)x^2 + (3y^2 - 5y + 1)x + (-4y + 7)

```

Into the input prompt, click OK. Observe pretty output.

# Answer
> 2 votes
## Python, 323 chars

```
I=raw_input().split()
print'%s(%s) ='%(I[0],','.join(I[1])),
def P(L,p,f):
 if type(L)==list:
  for i in range(len(L))[::-1]:P(L[i],p+[i],f);f=0
 elif L or f:A=abs(L);print'+-\0-'[2*f+(L<0)]+[(' %d '%A)[f:],' '][A==1and sum(p)>0]+' '.join([v,v+'^%d'%e][e>1]for v,e in zip(I[1],p)if e),
P(eval('['+','.join(I[2:])+']'),[],1)

```

# Answer
> 0 votes
## Python, 252 460 chars

Significantly longer than Keith Randall's, but matches the specifications better.
I copied `type(o)==list` from Keith. There are other similarities, but they were reached independently.
Sensitive to whitespace in the input. Particularly, space after `[` or before `]` breaks it.

```
e=lambda o,v,p:type(o)==list and[x for y in [e(c,v[1:],p+[(v[0],i)])for i,c in enumerate(o)]for x in y]or[(o,p)]
def f(x,y):z=" ".join(("%s^%d"%(a,b),a)[b<2]for a,b in y if b);return "+-"[x<0]+(" %d "%abs(x)," ")[z>"" and abs(x)==1]+z
l=raw_input().split()
t=" ".join(f(*x)for x in sorted(e(eval("["+",".join(l[2:])+"]"),l[1],[]),key=lambda x:[-dict(x[1]).get(a,0)for a in l[1]])if x[0])or'0'
print"%s(%s) = %s"%(l[0],",".join(l[1]),t[2*(t[0]=='+'):])

```

Logic:
Build a list of numbers/lists by replacing whitespace with commas and using `eval` (so `1 [2 3]` becomes `eval("[1,[2,3]]"`).
`e` converts the nested lists to a single list, with elements list `(3,[('x',2),('y',1)])` (for `3 x^2 y`).
I sort the list, with a key function that converts `('x',2),('y',1)` to `2,1`, by lexicographical order.
`f` prints each element in the list, preceded with `+`/`-`, and considering ones and zeros.
Just before printing, a preceding `+` is removed.

---
Tags: code-golf, polynomials
---


# Question
Title: Use NVM to tenaciously resume operation whenever aborted
## Summary

The aim of this challenge is to write a *tenacious* program. This is a stateful program designed to output a given string, but for which, if the program is aborted at any point during the writing of the string, rerunning the program will continue where it left off, writing only the characters that have not been written so far.

Specifically, the goal of this challenge is to output the string `01` using a tenacious program.

## Background

I once conjectured that with *n* cits, any string up to length 2<sup>(*n*-*k*)</sup> could be ouptut by a tenacious program, for some small fixed *k*. I'm now leaning toward thinking the goal can't be achieved :-(

This challenge, therefore, was designed to determine whether tenacious programs that output nontrivial strings are possible. `01` appears to be the shortest nontrivial goal string, and so is the subject of this challenge.

**Current status**: So far there are no correct answers, but it has been proven that 2 cits are not enough.

## Data storage

In order to store information across multiple runs of the program, you have access to a number of *cits*, bits made out of non-volatile memory; these are persistent, stateful bits that can have the value **0**, **1**, or **undefined**. They have the value **0** before the first execution of the program. If the program is aborted midway through writing a cit, that cit's value becomes **undefined** (unless the value being written to the cit was the value previously stored there), and will remain undefined until the program writes a **0** to the cit (and is not aborted midway through the write). Reading an **undefined** cit will (unpredictably) produce **0** or **1** (maybe different for each read), and your program must function correctly regardless of what values are read from **undefined** cits.

Each cit used by your program has a distinct address, which is an integer (you may choose how many cits are used, and what their addresses are). In order to read and write from the cits, you may assume that you have access to two functions: a function that takes a constant integer (representing the address of a cit), and returns a value read from that cit; and a function that takes an integer (representing the address of a cit) and a boolean (representing the value of a cit), and writes the value to the cit. These functions are guaranteed return in finite time (unless the program is aborted while they are running).

You may choose the names of this functions as appropriate for the language you are using. If the language uses identifiers as function names, the recommended names are `r` to read, `w` to write.

## Output

Due to the possibility that the program will be aborted during output, output from this challenge works a little differently from normal. Output may only be done a character at a time. You have access to a function that produces output in the following way: its argument is 0, 1, 2, or 3; if the given argument is the same as the argument to the previous call of the function (even in a previous execution of the program), or is 0 and no output has ever been produced, then the function does nothing. Otherwise, it outputs `0` if given an argument of 0 or 2, or `1` if given an argument of 1 or 3.

You may choose the name of this function as appropriate for the language you are using. If the language uses identifiers as function names, the recommended name is `p`.

## Requirements

Write a program with the following properties:

* The only state used by the program between runs is a number of cits (as defined above); all other storage used by the program must be initialised to a fixed value at the start of each run.
* The program will terminate in finite time, unless aborted.
* If all the cits used by the program start with value **0**, and then the program is run, aborted after an arbitrary length of time (which could occur at any moment during the program's execution, even while writing a cit or writing output), run again, aborted after another arbitrary length of time, and this process is repeated until the program terminates naturally, then (no matter what timing was used for the aborts) the combined output from all the program executions will be `01`.
* The program is single-threaded, making no use of parallelism or concurrency (this is required for the abort behaviour to be well-defined).

(More generally, a "tenacious program" is any program with the properties above, with `01` replaced with any arbitrary string. But this challenge is just about writing a tenacious program to output `01`.)

Alternatively, a proof that such a program is impossible is also considered a valid submission to this challenge.

You may alternatively write a function instead of a program, but it is only allowed to store state between calls via using cits; it cannot look at any of the state of the program that called it.

## Example

Here's an example of a C program that fails to solve the challenge:

```
// uses one cit with address 3
#include "hal.h"            // assumed to define r(), w(), p()
int main(void) {            // entry point, no parameters or input
    if (r(3)==0)            // cit 3 read as 0, that is state 0 or undefined
        w(3,0),             // write 0 to cit 3, to ensure it's defined
        p(2);               // put 2 with output '0' initially
    w(3,1),                 // mark we have output '0'
    p(1);                   // put 1 with output '1'
}                           // halt

```

To see why this doesn't work, imagine that the first run of the program is aborted during `w(3,1)`: this outputs `0`, and causes cit 3 to become **undefined**. Then imagine that the second run happens to read the undefined cit as **1**, and is aborted after `p(1)` completes (but before the program ends); at this point, the output is `01`. The cit is still **undefined**, because writing **1** to an **undefined** cit does not define it (only writing **0** can define it). A third run of the program might now happen to read the undefined cit as **0**, thus causing `0` and `1` to be output again. This produces the output `0101`, which is not `01`.

## Checking the validity of your solution

**@hammar** has written a checker that determines whether a given solution is valid (and/or explains why a particular solution isn't valid). To check your own solutions, or to see how it works, you can Try it online!.

## Victory condition

The program that achieves the requirements above using the fewest cits wins. In the case of a tie, programs which make fewer writes to cits per program execution are considered better (with the worst case more important than the best case); if there is still a tie, the shortest program (not counting the declarations of the provided functions) wins.

# Answer
While I don't have a solution nor a proof of impossibility, I figured I'd post my test harness for anyone wanting to play around with this, as I've pretty much given up at this point.

It's an implementation of the HAL modelling programs as a Haskell monad. It checks for tenacity by doing a breadth-first search over the possible sessions to check for sessions which either 1. have halted once without producing the correct output, or 2. have produced an output that is not a prefix of the desired one (this also catches programs producing infinite output).

```
{-# LANGUAGE GADTs #-}

module HAL where

import Control.Monad
import Data.List

import Data.Map (Map)
import qualified Data.Map as Map

import Data.Set (Set)
import qualified Data.Set as Set

newtype CitIndex = Cit Int
  deriving (Eq, Ord, Show)

data CitState = Stable Int | Unstable
  deriving (Eq, Ord, Show)

data Program a where
  Return :: a -> Program a
  Bind :: Program a -> (a -> Program b) -> Program b
  Put :: Int -> Program ()
  Read :: CitIndex -> Program Int
  Write :: CitIndex -> Int -> Program ()
  Log :: String -> Program ()
  Halt :: Program ()

instance Monad Program where
  return = Return
  (>>=) = Bind

data Session = Session
  { cits :: Cits
  , output :: [Int]
  , lastPut :: Int
  , halted :: Bool
  } deriving (Eq, Ord, Show)

data Event
  = ReadE CitIndex Int
  | PutE Int
  | WriteSuccessE CitIndex Int
  | WriteAbortedE CitIndex Int
  | LogE String
  | HaltedE
  deriving (Eq, Ord, Show)

type Log = [(Event, Cits)]

check :: Program () -> Int -> [Int] -> IO ()
check program n goal =
  case tenacity (program >> Halt) goal of
    Tenacious  -> putStrLn "The program is tenacious."
    Invalid ss -> do
      putStrLn "The program is invalid. Example sequence:"
      forM_ (zip [1..] ss) $ \(i, (log, s)) -> do
        ruler
        putStrLn $ "Run #" ++ show i ++ ", Initial state: " ++ formatState n s
        ruler
        mapM_ (putStrLn . formatEvent n) log
  where ruler = putStrLn $ replicate 78 '='

run :: Program a -> Session -> [(Maybe a, Log, Session)]
run (Return x) s = [(Just x, [], s)]
run (Bind x f) s = do
  (r1, l1, s1) <- run x s
  case r1 of
    Just y  -> [(r2, l1 ++ l2, s2) | (r2, l2, s2) <- run (f y) s1]
    Nothing -> [(Nothing, l1, s1)]
run (Put x) s = [(Just (), [(PutE x, cits s)], s')]
  where s' | lastPut s /= x = s { lastPut = x, output = output s ++ [x `mod` 2] }
           | otherwise      = s
run (Read cit) s =
  case lookupCit cit (cits s) of
    Stable x -> [(Just x, [(ReadE cit x, cits s)], s)]
    Unstable -> [(Just x, [(ReadE cit x, cits s)], s) | x <- [0, 1]]
run (Write cit x) (s @ Session { cits = cits }) =
  [(Just (), [(WriteSuccessE cit x, completed)], s { cits = completed }),
   (Nothing, [(WriteAbortedE cit x, aborted  )], s { cits = aborted })]
  where state = lookupCit cit cits
        completed = updateCit cit newState cits
          where newState = case (x, state) of
                             (0, _)        -> Stable 0
                             (1, Unstable) -> Unstable
                             (1, Stable _) -> Stable 1

        aborted = updateCit cit newState cits
          where newState = case (x, state) of
                             (0, Stable 0) -> Stable 0
                             (0, _)        -> Unstable
                             (1, Stable 1) -> Stable 1
                             (1, _)        -> Unstable
run (Halt) s = [(Just (), [(HaltedE, cits s)], s { halted = True })]
run (Log msg) s = [(Just (), [(LogE msg, cits s)], s)]

newSession :: Session
newSession = Session
  { cits = initialCits
  , output = []
  , lastPut = 0
  , halted = False }

newtype Cits = Cits (Map CitIndex CitState)
  deriving (Eq, Ord, Show)

initialCits = Cits (Map.empty)

lookupCit :: CitIndex -> Cits -> CitState
lookupCit cit (Cits m) = Map.findWithDefault (Stable 0) cit m

updateCit :: CitIndex -> CitState -> Cits -> Cits
updateCit index (Stable 0) (Cits m) = Cits $ Map.delete index m
updateCit index newState (Cits m) = Cits $ Map.insert index newState m

data Tenacity = Tenacious | Invalid [(Log, Session)]
  deriving (Eq, Ord, Show)

tenacity :: Program () -> [Int] -> Tenacity
tenacity program goal = bfs Set.empty [(newSession, [])]
  where
    bfs :: Set Session -> [(Session, [(Log, Session)])] -> Tenacity
    bfs visited [] = Tenacious
    bfs visited ((s, pred) : ss)
      | Set.member s visited = bfs visited ss
      | valid s   = bfs (Set.insert s visited) $ ss ++ [(s', (l, s) : pred) | (_, l, s') <- run program s]
      | otherwise = Invalid $ reverse (([], s) : pred)

    valid :: Session -> Bool
    valid Session { output = output, halted = halted }
      | halted    = output == goal
      | otherwise = output `isPrefixOf` goal

formatState :: Int -> Session -> String
formatState n s = "[cits: " ++ dumpCits n (cits s) ++ "] [output: " ++ dumpOutput s ++ "]"

formatEvent :: Int -> (Event, Cits) -> String
formatEvent n (event, cits) = pad (78 - n) text ++ dumpCits n cits
  where text = case event of
                 ReadE (Cit i) x         -> "read " ++ show x ++ " from cit #" ++ show i
                 PutE x                  -> "put " ++ show x
                 WriteSuccessE (Cit i) x -> "wrote " ++ show x ++ " to cit #" ++ show i
                 WriteAbortedE (Cit i) x -> "aborted while writing " ++ show x ++ " to cit #" ++ show i
                 LogE msg                -> msg
                 HaltedE                 -> "halted"

dumpCits :: Int -> Cits -> String
dumpCits n cits = concat [format $ lookupCit (Cit i) cits | i <- [0..n-1]]
  where format (Stable i) = show i
        format (Unstable) = "U"

dumpOutput :: Session -> String
dumpOutput s = concatMap show (output s) ++ " (" ++ show (lastPut s) ++ ")"

pad :: Int -> String -> String
pad n s = take n $ s ++ repeat ' '

```

Here is the example program given by the OP converted to Haskell.

```
import Control.Monad (when)

import HAL

-- 3 cits, goal is 01
main = check example 3 [0, 1]

example = do
  c <- Read (Cit 2)
  d <- Read (Cit c)
  when (0 == c) $ do
    Log "in first branch"
    Write (Cit 2) 0
    Write (Cit 1) 0
    Write (Cit 1) (1 - d)
    Write (Cit 2) 1
  Write (Cit 0) 0
  when (d == c) $ do
    Log "in second branch"
    Put 2
    Write (Cit 2) 0
  Write (Cit 0) 1
  Put 1

```

And here is the corresponding output, showing that the program is not tenacious.

```
The program is invalid. Example sequence:
==============================================================================
Run #1, Initial state: [cits: 000] [output:  (0)]
==============================================================================
read 0 from cit #2                                                         000
read 0 from cit #0                                                         000
in first branch                                                            000
wrote 0 to cit #2                                                          000
wrote 0 to cit #1                                                          000
wrote 1 to cit #1                                                          010
wrote 1 to cit #2                                                          011
wrote 0 to cit #0                                                          011
in second branch                                                           011
put 2                                                                      011
wrote 0 to cit #2                                                          010
wrote 1 to cit #0                                                          110
put 1                                                                      110
halted                                                                     110
==============================================================================
Run #2, Initial state: [cits: 110] [output: 01 (1)]
==============================================================================
read 0 from cit #2                                                         110
read 1 from cit #0                                                         110
in first branch                                                            110
wrote 0 to cit #2                                                          110
wrote 0 to cit #1                                                          100
wrote 0 to cit #1                                                          100
aborted while writing 1 to cit #2                                          10U
==============================================================================
Run #3, Initial state: [cits: 10U] [output: 01 (1)]
==============================================================================
read 1 from cit #2                                                         10U
read 0 from cit #1                                                         10U
wrote 0 to cit #0                                                          00U
aborted while writing 1 to cit #0                                          U0U
==============================================================================
Run #4, Initial state: [cits: U0U] [output: 01 (1)]
==============================================================================
read 0 from cit #2                                                         U0U
read 0 from cit #0                                                         U0U
in first branch                                                            U0U
wrote 0 to cit #2                                                          U00
wrote 0 to cit #1                                                          U00
wrote 1 to cit #1                                                          U10
wrote 1 to cit #2                                                          U11
wrote 0 to cit #0                                                          011
in second branch                                                           011
put 2                                                                      011
wrote 0 to cit #2                                                          010
wrote 1 to cit #0                                                          110
put 1                                                                      110
halted                                                                     110
==============================================================================
Run #5, Initial state: [cits: 110] [output: 0101 (1)]
==============================================================================

```
> 6 votes

# Answer
Unless someone can find a bug in this program, I think it checks and rejects every relevant two-cit program.

I argue that it suffices to consider programs which read all the cits and switch on a number formed by the set. Each branch of the switch will be a series of writes and puts. There's never any point putting the same number more than once in a branch, or putting the second output digit before the first one. (I'm morally certain that there's no point outputting the first digit other than at the start of a branch or the second digit other than at the end, but for now I'm avoiding that simplification).

Then each branch has a target set of cits it wants to set, and moves towards it by setting the bits it wants to be 0 as 0, and the bits it wants to be 1 as 0 then 1; these write operations can be ordered in various ways. There's no point setting a bit to 1 unless you've already set it to 0 in that run, or it's likely a nop.

It considers 13680577296 possible programs; it took a 4-core machine just under 7 hours to check them all without finding a single solution.

```
import java.util.*;

// State is encoded with two bits per cit and two bits for the output state.
//    ... [c_2=U][c_2=1/U][c_1=U][c_1=1/U][output_hi][output_lo]
// Output state must progress 0->1->2.
// Instruction (= program branch) is encoded with three or four bits per step.
//      The bottom two bits are the cit, or 0 for output/loop
//      If they're 0, the next two bits are 01 or 10 for output state, or 11 for halt.
//      Otherwise the next two bits are the value to write to the cit.
public class CitBruteForcer implements Runnable {

    static final int[] TRANSITION_OK = new int[]{
        // Index: write curr_hi curr_lo
        0,  // write 0 to 0 => 0
        0,  // write 0 to 1 => 0
        0,  // write 0 to U => 0
        -1, // invalid input
        1,  // write 1 to 0 => 1
        1,  // write 1 to 1 => 1
        2,  // write 1 to U => U
        -1  // invalid input
    };
    static final int[] TRANSITION_ABORT = new int[]{
        // Index: write curr_hi curr_lo
        0,  // write 0 to 0 => 0
        2,  // write 0 to 1 => U
        2,  // write 0 to U => U
        -1, // invalid input
        2,  // write 1 to 0 => U
        1,  // write 1 to 1 => 1
        2,  // write 1 to U => U
        -1  // invalid input
    };

    private final int[] possibleInstructions;
    private final int numCits, offset, step;
    private long tested = 0;

    private CitBruteForcer(int numCits, int[] possibleInstructions, int offset, int step)
    {
        this.numCits = numCits;
        this.possibleInstructions = possibleInstructions;
        this.offset = offset;
        this.step = step;
    }

    public void run()
    {
        int numStates = 1 << numCits;
        int n = possibleInstructions.length;
        long limit = pow(n, numStates);

        for (long i = offset; i < limit; i += step) {
            // Decode as a base-n number.
            int[] instructions = new int[numStates];
            long tmp = i;
            for (int j = 0; j < numStates; j++, tmp /= n) instructions[j] = possibleInstructions[(int)(tmp % n)];
            Program p = new Program(numCits, instructions);
            if (p.test()) System.out.println("Candidate: " + i);
            tested++;
        }
    }

    public static void main(String[] args) {
        int numCits = 2;
        int numThreads = 4;
        int[] possibleInstructions = buildInstructions(numCits);

        int numStates = 1 << numCits;
        int n = possibleInstructions.length;
        System.out.println(n + " possible instructions");
        long limit = pow(n, numStates);

        CitBruteForcer[] forcers = new CitBruteForcer[numThreads];
        for (int i = 0; i < numThreads; i++) {
            forcers[i] = new CitBruteForcer(numCits, possibleInstructions, i, numThreads);
            new Thread(forcers[i]).start();
        }

        int pc = 0;
        while (pc < 100) {
            // Every 10 secs is easily fast enough to update
            try { Thread.sleep(10000); } catch (InterruptedException ie) {}

            long tested = 0;
            for (CitBruteForcer cbf : forcers) tested += cbf.tested; // May underestimate because the value may be stale
            int completed = (int)(100 * tested / limit);
            if (completed > pc) {
                pc = completed;
                System.out.println(pc + "% complete");
            }
        }
        System.out.println(limit + " programs tested");
    }

    private static int[] buildInstructions(int numCits) {
        int limit = (int)pow(3, numCits);
        Set<Integer> instructions = new HashSet<Integer>();
        for (int target = 0; target <= limit; target++) {
            int toSetZero = 0, toSetOne = 0;
            for (int i = 0, tmp = target; i < numCits; i++, tmp /= 3) {
                if (tmp % 3 == 0) toSetZero |= 1 << i;
                else if (tmp % 3 == 1) toSetOne |= 1 << i;
            }
            buildInstructions(0xc, toSetZero, toSetOne, false, false, instructions);
        }
        int[] rv = new int[instructions.size()];
        Iterator<Integer> it = instructions.iterator();
        for (int i = 0; i < rv.length; i++) rv[i] = it.next().intValue();
        return rv;
    }

    private static void buildInstructions(int suffix, int toSetZero, int toSetOne, boolean emitted0, boolean emitted1, Set<Integer> instructions)
    {
        if (!emitted1) {
            buildInstructions((suffix << 4) + 0x8, toSetZero, toSetOne, false, true, instructions);
        }
        if (!emitted0) {
            buildInstructions((suffix << 4) + 0x4, toSetZero, toSetOne, true, true, instructions);
        }
        if (toSetZero == 0 && toSetOne == 0) {
            instructions.add(suffix);
            return;
        }

        for (int i = 0; toSetZero >> i > 0; i++) {
            if (((toSetZero >> i) & 1) == 1) buildInstructions((suffix << 3) + 0x0 + i+1, toSetZero & ~(1 << i), toSetOne, emitted0, emitted1, instructions);
        }
        for (int i = 0; toSetOne >> i > 0; i++) {
            if (((toSetOne >> i) & 1) == 1) buildInstructions((suffix << 3) + 0x4 + i+1, toSetZero | (1 << i), toSetOne & ~(1 << i), emitted0, emitted1, instructions);
        }
    }

    private static long pow(long n, int k) {
        long rv = 1;
        while (k-- > 0) rv *= n;
        return rv;
    }

    static class Program {
        private final int numCits;
        private final int[] instructions;
        private final Set<Integer> checked = new HashSet<Integer>();
        private final Set<Integer> toCheck = new HashSet<Integer>();

        Program(int numCits, int[] instructions) {
            this.numCits = numCits;
            this.instructions = (int[])instructions.clone();
            toCheck.add(Integer.valueOf(0));
        }

        boolean test() {
            try {
                while (!toCheck.isEmpty()) checkNext();
            } catch (Exception ex) {
                return false;
            }

            // Need each reachable state which hasn't emitted the full output to be able to reach one which has.
            Set<Integer> reachable = new HashSet<Integer>(checked);
            for (Integer reached : reachable) {
                checked.clear();
                toCheck.clear();
                toCheck.add(reached);
                while (!toCheck.isEmpty()) checkNext();
                boolean emitted = false;
                for (Integer i : checked) {
                    if ((i.intValue() & 3) == 2) emitted = true;
                }
                if (!emitted) return false;
            }

            return true;
        }

        private void checkNext() {
            Integer state = toCheck.iterator().next();
            toCheck.remove(state);
            checked.add(state);
            run(state.intValue());
        }

        private void run(final int state) {
            // Check which instructions apply
            for (int i = 0; i < instructions.length; i++) {
                boolean ok = true;
                for (int j = 1; j <= numCits; j++) {
                    int cit = (state >> (2 * j)) & 3;
                    if (cit == 2 || cit == ((i >> (j-1)) & 1)) continue;
                    ok = false; break;
                }
                if (ok) run(state, instructions[i]);
            }
        }

        private void run(int state, int instruction) {
            while (true) {
                int cit = instruction & 3;
                if (cit == 0) {
                    int emit = (instruction >> 2) & 3;
                    if (emit == 3) break;
                    if (emit > (state & 3) + 1 || emit < (state & 3)) throw new IllegalStateException();
                    state = (state & ~3) | emit;
                    instruction >>= 4;
                }
                else {
                    int shift = 2 * cit;
                    int transitionIdx = (instruction & 4) + ((state >> shift) & 3);
                    int stateMasked = state & ~(3 << shift);
                    consider(stateMasked | (TRANSITION_ABORT[transitionIdx] << shift));
                    state = stateMasked | (TRANSITION_OK[transitionIdx] << shift);
                    instruction >>= 3;
                }
                // Could abort between instructions (although I'm not sure this is strictly necessary - this is "better" than the mid-instruction abort
                consider(state);
            }
            // Halt or loop.
            consider(state);
        }

        private void consider(int state) {
            if (!checked.contains(state)) toCheck.add(state);
        }
    }
}

```
> 4 votes

# Answer
This is was my best attempt at answering my own question. I am uncertain that it meets requirement 3, and am open to refutation. It is not tenacious :-(

```
/*  1 */    #include "hal.h"
/*  2 */    main(){
/*  3 */        unsigned c = r(2);  // get cit 2 into c
/*  4 */        unsigned d = r(c);  // get cit c into d
/*  5 */    // here if d==c then we have not output 1 yet
/*  6 */    //              else we have     output 0
/*  7 */        if (0==c)
/*  8 */            w( 2, 0 ),      // cit 2 to 0
/*  9 */            w( 1, 0 ),      // cit 1 to 0
/* 10 */            w( 1,!d ),      // cit 1 to complement of d
/* 11 */            w( 2, 1 );      // cit 2 to 1
/* 12 */        w( 0, 0 );          // cit 0 to 0
/* 13 */        if (d==c)
/* 14 */            p( 2 ),         // put 2, first one outputs 0
/* 15 */            w( 2, 0 );      // cit 2 to 0
/* 16 */        w( 0, 1 );          // cit 0 to 1
/* 17 */        p( 1 );             // put 1, first one outputs 1
/* 16 */    }                       // halt

```
> 0 votes

---
Tags: code-challenge, stateful
---


title: Shortest ELF for "Hello world\n"?

text:
# Question
Title: Shortest ELF for "Hello world\n"?
Is it possible to write (pack) a shorter than 145 bytes version of a program with "Hello world" (plus new line) output if the length of the program is measured as a number of bytes in program's ELF (x86) representation? Reduction technique in mind is described here:

1. http://timelessname.com/elfbin/
2. http://www.muppetlabs.com/~breadbox/software/tiny/teensy.html

Please reply with providing a code example. Note,  says "Hi world" and \[2\] returns 42 instead of an output, hence I assume current solution to be *142 + (len("Hello") - len("Hi"))* which is **145**.

**\[EDIT\]**

**Limits of ELF**: syntactically a program translated into ELF is determined by its interpreter (libc), which is a combination of:

* Target architecture (Generic, AMD64, ARM, IA-32, MIPS, etc.)
* OS kernel (which communicates with implementation of ELF interpreter and often is itself packed into an ELF binary)

From TIS spec. 1.2

> There is one valid program interpreter for programs conforming to the ELF specification for the Intel architecture: /usr/lib/libc.so.1

In theory - all clear - multiple combinations times version differences (Arch, OS) are possible. In practice - because standard is less strict than any BNF for CFG or other finer (smaller) formal language - there can be implementation differences (options) including shorter length of the program.

On one hand, because ELF is not that precise (one naturally expects) it is much more difficult to do code-golf with it. Hence a "Hello world\n" program is expected to be by default in **TIS ELF 1.2, x86 (Generic Intel), Linux 2.6.(20+)**. On the other hand having a shorter ELF that runs e.g. on \*BSD seems like an extremely valuable knowledge to me!

For example ELF64 (latest draft) is much more interesting incl. the differences with ELF(x86). So, *please* share a solution that can be accepted with correction to specific configuration.

*Motivation*: It is the practical part that is interesting for me and code-golf is a very nice way to show how tricky it is to come up with any machine- (or even byte) code in general and why ELF does apparently such a good job (in my understanding). Thus a golf solution is not only cool per say but also can provide a practical knowledge of unexpected interpretation differences of ELF (if an alternative combination is given).

# Answer
> 22 votes
Even if you require full adherence to the ELF specification, you can squeeze it into 98 bytes:

```
            org     0x04B34000
            db      0x7F, "ELF", 1, 1, 1, 0 ; e_ident
            dd      0, 0
            dw      2                       ; e_type
            dw      3                       ; e_machine
            dd      1                       ; e_version
            dd      _start                  ; e_entry
            dd      phdr - $$               ; e_phoff
            dd      0                       ; e_shoff
            dd      0                       ; e_flags
            dw      0x34                    ; e_ehsize
            dw      0x20                    ; e_phentsize
phdr:       dd      1                       ; e_phnum       ; p_type
                                            ; e_shentsize
            dd      0                       ; e_shnum       ; p_offset
                                            ; e_shstrndx
            db      0                                       ; p_vaddr
_start:     inc     eax
            mov     bl, 4
            mov     dl, 12                                  ; p_paddr
            jmp     short part2
            dd      filesize                                ; p_filesz
            dd      filesize                                ; p_memsz
            dd      5                                       ; p_flags
            dd      0x1000                                  ; p_align
str:        db      'Hello world', 10
part2:      mov     ecx, str
again:      xchg    eax, ebx
            int     0x80
            jmp     short again
filesize    equ     $ - $$

```

Or if you prefer hex bytes: `7F 45 4C 46 01 01 01 00 00 00 00 00 00 00 00 00 02 00 03 00 01 00 00 00 35 40 B3 04 2C 00 00 00 00 00 00 00 00 00 00 00 34 00 20 00 01 00 00 00 00 00 00 00 00 40 B3 04 B2 0C EB 1C 62 00 00 00 62 00 00 00 05 00 00 00 00 10 00 00 48 65 6C 6C 6F 20 77 6F 72 6C 64 0A B9 4C 40 B3 04 93 CD 80 EB FB`

The ELF specification explicitly permits different sections to overlap, so it is perfectly legal to let the program segment header table share bytes with the ELF header. Furthermore, the x86 version of the ELF standard states that the p\_paddr field is *ignored*, as opposed to merely being *unused* (which typically comes with the requirement that it be set to zero. Thus it is safe to contain arbitrary bytes.

Finally, three more bytes are saved by overlapping the code with the load address.

# Answer
> 11 votes
Looking at link \[2\] A Whirlwind Tutorial on Creating Really Teensy ELF Executables for Linux, by appending the literal string 'Hello, world!' to the end (instead of letting the last 7 bytes auto fill with zeros), you should be able to squeeze it to 59 bytes, assuming your print logic isn't longer than 8 bytes.

In fact, the user 'breadbox', who I assume to be the writer of the post, has posted a 57 byte version on anarchy golf. It might be useful to look at some of his other post mortems: they seem to be all ELF format.

### EDIT: 61 bytes

Using breadbox's nested header approach, I was able to produce this 61 byte solution:

```
BITS 32
        org     0x05000000
        db      0x7F, "ELF"
        dd      1
        dd      0
        dd      $$
        dw      2
        dw      3
        dd      0x0500001B
        dd      0x0500001B
        dd      4
        mov     dl, 12
        mov     ecx, msg
        int     0x80
        db      0x25
        dw      0x20
        dw      0x01
        inc     eax
        int     0x80
msg     db      'Hello world', 10

```

Assemble as:

```
nasm -fbin hello.asm
chmod +x hello
./hello

```

Producing:

```
00000000  7f 45 4c 46 01 00 00 00  00 00 00 00 00 00 00 05  |.ELF............|
00000010  02 00 03 00 1b 00 00 05  1b 00 00 05 04 00 00 00  |................|
00000020  b2 0c b9 31 00 00 05 cd  80 25 20 00 01 00 40 cd  |...1.....% ...@.|
00000030  80 48 65 6c 6c 6f 20 77  6f 72 6c 64 0a           |.Hello world.|

```

The code begins at 0x001B:

```
0540000000      add     eax, 0x00000004    ;sys_write
B20C            mov     dl,  12            ;message length
B92E000005      mov     ecx, msg           ;message pointer
CD80            int     0x80               ;syscall
2520000100      and     eax, 0x00010020    ;clears eax
40              inc     eax                ;sys_exit
CD80            int     0x80               ;syscall

```

The 32-bit `add` is necessary (instead of `mov al, 4` for example), because it's also used as the program header offset, and needs to be exactly 4 (where the program header starts in the above code). The `and` later on is used to clear eax, because 0x20 and 0x01 are unavoidable header values.

### EDIT: 111 bytes (with proper headers)

If, on the other hand, you'd rather your headers adhere to the ELF specifications (even if your kernel ignores them), you could use this instead:

```
BITS 32
            org     0x08048000
ehdr:                                               ; Elf32_Ehdr
            db      0x7F, "ELF", 1, 1, 1, 0         ;   e_ident
    times 8 db      0
            dw      2                               ;   e_type
            dw      3                               ;   e_machine
            dd      1                               ;   e_version
            dd      _start                          ;   e_entry
            dd      phdr - $$                       ;   e_phoff
            dd      0                               ;   e_shoff
            dd      0                               ;   e_flags
            dw      ehdrsize                        ;   e_ehsize
            dw      phdrsize                        ;   e_phentsize
            dw      1                               ;   e_phnum
            dw      0                               ;   e_shentsize
            dw      0                               ;   e_shnum
            dw      0                               ;   e_shstrndx
ehdrsize    equ     $ - ehdr

phdr:                                               ; Elf32_Phdr
            dd      1                               ;   p_type
            dd      0                               ;   p_offset
            dd      $$                              ;   p_vaddr
            dd      $$                              ;   p_paddr
            dd      filesize                        ;   p_filesz
            dd      filesize                        ;   p_memsz
            dd      5                               ;   p_flags
            dd      0x1000                          ;   p_align
phdrsize    equ     $ - phdr

_start:     mov     al, 4
            mov     dl, msg_len
            mov     ecx, msg
            int     0x80
            mov     al, 1
            int     0x80

msg         db      'Hello world', 10
msg_len     equ     $ - msg

filesize    equ     $ - $$

```

It's tempting to overlap the last 8 bytes of the ehdr with the first 8 bytes of the phdr, since they are identical (and therefore, all headers would be correct), but in the spirit of being proper, I decided not to.

This assembles to a 111 byte solution:

```
00000000  7f 45 4c 46 01 01 01 00  00 00 00 00 00 00 00 00  |.ELF............|
00000010  02 00 03 00 01 00 00 00  54 80 04 08 34 00 00 00  |........T...4...|
00000020  00 00 00 00 00 00 00 00  34 00 20 00 01 00 00 00  |........4. .....|
00000030  00 00 00 00 01 00 00 00  00 00 00 00 00 80 04 08  |................|
00000040  00 80 04 08 6f 00 00 00  6f 00 00 00 05 00 00 00  |....o...o.......|
00000050  00 10 00 00 b0 04 b2 0c  b9 63 80 04 08 cd 80 b0  |.........c......|
00000060  01 cd 80 48 65 6c 6c 6f  20 77 6f 72 6c 64 0a     |...Hello world.|

```

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


title: Sort an array with values of integer

text:
# Question
Title: Sort an array with values of integer
There is an array of integer values to be sorted.During the sorting process, the places of two numbers can be interchanged. Each interchange has a cost, which is the sum of the two numbers involved.

You must write a program that determines the minimal cost to sort the sequence of numbers.

# Answer
### Scala:

```
def minimalCostToSortArray (daArray: Array[Int]) = 0

```

Why is the cost always zero? Because I don't change numbers at all:

```
def arrsort (a: Array[Int], pos:Int = 0): Array[Int] = {
  if (pos >= a.length -1) a else {
    if (a(pos) > a(pos+1)) {
      val diff = a(pos) - a(pos+1)
      a (pos) -= diff
      a (pos+1) += diff
      arrsort (a)
    } else arrsort (a, pos+1)
  }
}

```
> 7 votes

---
Tags: arithmetic, sorting
---


title: Solve the 14-Pegs puzzle

text:
# Question
Title: Solve the 14-Pegs puzzle
## Introduction

A common puzzle involves a triangular board with 15 holes for tees/pegs as shown in the image below:

Starting with all the pegs in the board except for a hole at the top, the point of the puzzle is to jump pegs over one another like checkers in such a way to leave exactly one peg left. The only valid move is to jump one peg over an adjacent peg in any direction into an empty hole. The peg that was jumped is then removed from the board. Play finishes when there remain no valid moves.

## Spec

Your job is to write a program that can find a complete solution to the peg puzzle, i.e., one that leaves exactly one peg left. There are multiple possible solutions, so your program just needs to print one.

* Your program will receive no input. You are not allowed to read data from any outside source.
* Print out the list of 13 moves that gives a result of 1 peg remaining using this format:
> `Peg 1 jumps Peg 3 to Hole 6.`
* The holes/pegs are numbered from top to bottom, left to right, so that the top peg/hole is 1, numbering until the bottom-right is 15.
* Your program **must** find the solution *at runtime*. Printing out a solution directly by any means other than solving it in the program is an automatic disqualification.
* **Bonus**: receive 10 bonus points if you can output multiple unique solutions (can just print separated by blank lines).
* **Bonus**: receive 5 bonus points if the number `15` appears nowhere in your source code.

## Scoring

This is code-golf, so the shortest solution (by byte count) that prints out a correct answer will be the winner. Bonus points are subtracted from your total byte count. Please provide a sample output of running your program as well as a link to `ideone` or some similar site if possible demonstrating the execution of your program.

# Answer
### Ruby, score 240 238 234 = 249 - 10 - 5

```
s=->t,r,c{c>0?(t+t.reverse).gsub(/[A-O]{2}[a-o]/){|j|s[t.tr(j,j.swapcase),r+"Peg #{j[0].ord-64} jumps Peg #{j[1].ord-64} to Hole #{j[2].ord-96}.\n",c-1]}:$><<r+"\n"}
s["aBD,BDG,DGK,CEH,EHL,FIM,aCF,CFJ,FJO,BEI,EIN,DHM,DEF,GHI,HIJ,KLM,LMN,MNO,","",13]

```

A plain ruby implementation which prints all possible solutions to this puzzle (takes less than a minute on my computer). The first lines of output can be seen here:

```
Peg 6 jumps Peg 3 to Hole 1.
Peg 4 jumps Peg 5 to Hole 6.
Peg 1 jumps Peg 2 to Hole 4.
Peg 14 jumps Peg 9 to Hole 5.
Peg 7 jumps Peg 8 to Hole 9.
Peg 12 jumps Peg 13 to Hole 14.
Peg 10 jumps Peg 6 to Hole 3.
Peg 4 jumps Peg 5 to Hole 6.
Peg 3 jumps Peg 6 to Hole 10.
Peg 15 jumps Peg 10 to Hole 6.
Peg 6 jumps Peg 9 to Hole 13.
Peg 14 jumps Peg 13 to Hole 12.
Peg 11 jumps Peg 12 to Hole 13.

Peg 6 jumps Peg 3 to Hole 1.
Peg 4 jumps Peg 5 to Hole 6.
Peg 1 jumps Peg 2 to Hole 4.
Peg 14 jumps Peg 9 to Hole 5.
Peg 7 jumps Peg 8 to Hole 9.
...

```

And the online example can be found here.
> 8 votes

# Answer
## Python, 324 chars, score = 319

```
f=0xf
x=0x12413624725935836a45647b48d58c59e69d6af78989abcdcdedef
Z=[(x>>12*i&f,x>>12*i+4&f,x>>12*i+8&f)for i in range(18)]
M=[[65532,'']]
for i in' '*13:
 Q=[]
 for p,m in M:
  for a,b,c in[x[::-1]for x in Z]+Z:
   if p>>a&p>>b&~p>>c&1:Q+=[[p^2**a^2**b^2**c,m+"Peg %d jumps Peg %d to Hole %d.\n"%(a,b,c)]]
 M=Q
print M[0][1]

```

The peg state is kept as a bitmask. `M` contains a list of peg states and the instructions to get to that state.

I could make it print out all of the solutions as well (there are 29760 of them), but it would cost more than 10 characters to do it.

I can't post it on ideone as it takes about 90 seconds to run.

Output:

```
Peg 6 jumps Peg 3 to Hole 1.
Peg 4 jumps Peg 5 to Hole 6.
Peg 1 jumps Peg 2 to Hole 4.
Peg 14 jumps Peg 9 to Hole 5.
Peg 12 jumps Peg 13 to Hole 14.
Peg 7 jumps Peg 8 to Hole 9.
Peg 10 jumps Peg 6 to Hole 3.
Peg 4 jumps Peg 5 to Hole 6.
Peg 3 jumps Peg 6 to Hole 10.
Peg 15 jumps Peg 10 to Hole 6.
Peg 6 jumps Peg 9 to Hole 13.
Peg 14 jumps Peg 13 to Hole 12.
Peg 11 jumps Peg 12 to Hole 13.

```
> 3 votes

# Answer
**C, 386 chars, score = 371**

```
int f[37],o[36],t[36],r[14],i[14],m=1,s=~3,j=18;main(){while(j--)o[j]=o[18+j]=(f[j]=t[18+j]="AABBCCDDDEEFFGHKLM"[j]-64)+(t[j]=f[18+j]="DFGIHJKMFLNMOIJMNO"[j]-64)>>1;while(m)if(!f[++j])s=r[--m],j=i[m];else if(s>>f[j]&s>>o[j]&~s>>t[j]&1)if(r[m]=s,s^=1<<f[j]|1<<o[j]|1<<t[i[m]=j],j=-1,++m>13)for(m=printf("\n");m<14;++m)printf("Peg %d jumps Peg %d to Hole %d.\n",f[i[m]],o[i[m]],t[i[m]]);}

```

Prints out all 29760 solutions, in well under a second.

This version assumes (among other things) that the compiler will permit the implicit declaration of printf(). About six more characters could be saved by making use of implicit-int, but that feature was technically removed from C99.

Also, four more bytes can be saved by replacing the capital letters in the two strings with the corresponding control characters. I didn't do that here because compilers aren't required to permit such strings, and it makes already-dense source code completely illegible.

For clarity, here's the same algorithm without the more obfuscatory size-optimizations:

```
#include <stdio.h>
int f[37], o[36], t[36], r[14], i[14], m, j, s = ~3;
int main(void)
{
    for (j = 0 ; j < 18 ; ++j) {
        f[j] = t[18+j] = "AABBCCDDDEEFFGHKLM"[j] - 64;
        t[j] = f[18+j] = "DFGIHJKMFLNMOIJMNO"[j] - 64;
        o[j] = o[18+j] = (f[j] + t[j]) >> 1;
    }
    j = 0;
    for (m = 1 ; m ; ++j) {
        if (!f[j]) {
            --m;
            s = r[m];
            j = i[m];
        } else if ((s >> f[j]) & (s >> o[j]) & (~s >> t[j]) & 1) {
            r[m] = s;
            i[m] = j;
            s ^= (1 << f[j]) | (1 << o[j]) | (1 << t[j]);
            j = -1;
            ++m;
            if (m > 13) {
                printf("\n");
                for (m = 1 ; m < 14 ; ++m)
                    printf("Peg %d jumps Peg %d to Hole %d.\n",
                           f[i[m]], o[i[m]], t[i[m]]);
            }
        }
    }
    return 0;
}

```

f, o, and t are the list of legal jumps initialized in the first loop. r and i form the history that the program uses to backtrack and explore all possible games.

I'm sure this can be improved!
> 3 votes

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


# Question
Title: Implement wc (word count) shortest code wins
Write a stripped down version of the wc command. The program can simply open a file which does not need to be configurable or read from stdin until it encounters the end of file. When the program is finished reading, it should print:

* \# bytes read
* \# characters read
* \# lines read
* max line length
* \# words read

Program must at least work with ascii but bonus points if it works on other encodings.

Shortest code wins.

# Answer
## Haskell - 80 characters

```
l=length
main=interact$ \s->show$map($s)[l,l,l.lines,maximum.map l.lines,l.words]

```
> 11 votes

# Answer
# Perl - 71

```
$c+=$x=y!!!c,$w+=split,$m=$m<$x?$x-1:$m,$l++for<>;say"$c,$c,$l,$m,$w"

```

I think it can be shortened further but I don't know how.

(edit: used Zaid's suggestion)
(edit 2: changed `length` to `y!!!c`)
(edit 3: changed `print` to `say`)
> 6 votes

# Answer
## c -- 214

Implementation is almost right out of K&R. Relies on K&R semantics for main (unspecified return type), but I think it otherwise conforms to c89. Output format is specified below (but it assumes that chars == bytes).

```
#include <stdio.h>
int b,w,l,t,L;main(int c,char**v){FILE*f=fopen(v[1],"r");for(;(c=getc(f))
!=-1;++b){t++;if(c=='\n')l++,L=t>L?t:L,t=0;else if(c==' '||c=='\t')w++;}
L=t>L?t:L;printf("%d (%d) %d %d %d\n",l,L,w,b,b);}

```

There is some ambiguity in the meaning of "words" as yet. This version defines words as breaking only on `'[ \t\n]` and does not account for a word that ends with EOF. This will work for files following the old unix convention of always ending with a newline, but break for those that stop hard on EOF.

It *does* test lines that end of EOF for maximal length.

## Un-golfed

```
#include <stdio.h>
int b, /* bytes */
  w, /* words */
  l, /* lines */
  t, /*this line*/
  L; /* longest line */
main(int c,char**v){
  FILE*f=fopen(v[1],"r");
  for(;(c=getc(f))!=-1;++b){
    t++;
    if(c=='\n') l++, L = t>L ? t : L, t=0;
    else if(c==' '||c=='\t')w++;
  }
  L = t>L ? t : L;
  /* Output format is lines (max line length) words chars bytes */
  printf("%d (%d) %d %d %d\n",l,L,w,b,b);
}

```

## Validation

```
$ gcc -o wc wordcount_golf.c
$ ./wc wordcount.c
17 (67) 82 410 410
$ ./wc wordcount_golf.c
4 (74) 9 217 217
$ wc wordcount.c
 17  67 410 wordcount.c
$ wc wordcount_golf.c
  4  13 217 wordcount_golf.c

```
> 5 votes

# Answer
# ruby (72 characters)

```
t=readlines;s=t*'';p [s.size]*2+[t.size,t.map(&:size).max,s.split.size]

```

This solution uses a functional style similar to trinithis's Haskell solution.

I assume ASCII text and space-separated words.
> 3 votes

# Answer
# awk - 58

```
awk 'x=1+length{w+=NF;if(m<x)m=x;c+=x}END{print NR,w,c,m}'

```
> 3 votes

# Answer
# Groovy, ~~85~~ 81

```
a={it.size()};[s=a(t=f.text),s,a(z=t.split"\n"),z*.size().max(),a(t.split(/\s/))]

```
> 2 votes

# Answer
# Perl - 66 characters

```
for(<>){$t+=$l=y!!!c,$m=$l-1if$m<$l,$w+=split}say"$. $w $t $m $t"

```

I managed to save a couple of bytes by letting Perl handle the number of lines, using the $. variable. Other than that, even without looking, I ended up with what Marinus got, for the most part.

Here's the program I used to verify it:

```
#!/bin/bash

function test1() {
    cat <<EOF
Lorem ipsum dolor sit amet,
consectetur adipiscing elit. Duis eget
neque vel ipsum porta bibendum
dictum in ante. Ut accumsan
magna id nisl bibendum et
tincidunt turpis eleifend. Duis nec
mi hendrerit lorem hendrerit convallis.
Quisque sit amet tincidunt diam.
Sed vehicula velit sed risus
pellentesque vitae auctor nisi semper.
Nulla erat massa, semper sit
amet luctus non, bibendum id
eros. Etiam non lacus odio.
Donec vitae nisl vitae nisi
elementum suscipit. Cras ut mollis
mauris.
EOF
}

function test2() {
    cat <<EOF
Curabitur quis elit turpis. Vestibulum
ut elementum magna. Lorem ipsum
dolor sit amet, consectetur adipiscing
elit. Nam sit amet quam
ante. Nullam in risus est,
quis cursus magna. Vestibulum feugiat
nisl nec velit scelerisque molestie.
Pellentesque habitant morbi tristique senectus
et netus et malesuada fames
ac turpis egestas. Vestibulum feugiat
sem vitae mauris aliquet eget
ullamcorper velit molestie.
EOF
}

function test3() {
    cat <<EOF
Proin diam elit, imperdiet id
gravida et, facilisis nec lectus.
Nullam placerat enim sed nulla
porttitor hendrerit. Praesent eu quam
enim, et commodo orci. Nam
eu purus ut ipsum malesuada
rhoncus vitae ut turpis. Morbi
a risus eu ligula faucibus
tincidunt. Cum sociis natoque penatibus
et magnis dis parturient montes,
nascetur ridiculus mus. Nulla faucibus
vehicula diam at tempus. Aliquam
tristique, erat vel fringilla scelerisque,
magna purus venenatis nulla, at
elementum mi lectus vitae nibh.
Phasellus nibh neque, tempus commodo
pretium eget, gravida quis felis.
Vivamus venenatis tristique volutpat. Nunc
vulputate accumsan magna, sit amet
vehicula orci imperdiet vel. Nam
vitae laoreet purus.
EOF
}

PROG1=wc
PROG2='perl5.14.2 -Mv5.10 wc-golfed.pl'

for((i=1;i<4;i++)); do
    wc=( $(test$i | $PROG1) )
    golf=( $(test$i | $PROG2) )
    for((j=0;j<2;j++)); do
    if [ ! ${wc[$j]} = ${golf[$j]} ]; then
        echo "Test #$i failed"
        echo "     wc: ${wc[@]}"
        echo "   golf: ${golf[@]}"
        continue 2
    fi
    done
    echo "Test #$i passed"
done

```
> 2 votes

# Answer
## C - 164 chars

This is based on dmckee's code with FUZxxl's improvements, but shortened further and converted to standard C. The code reads from standard input only. Any sequence of one or more consecutive characters with ASCII code \>= 33 is counted as a word.

```
#include<stdio.h>
int b,w,l,t,L,c,s;int main(void){for(;c=getchar()+1;++b)t-=c==11?l++,t>L?L=t:t:-1,s=c>33?w+=!s:0;printf("%d %d %d %d\n",l,t>L?t:L,w,b);return 0;}

```

## Un-golfed

```
#include <stdio.h>
int b, /* bytes */
     w, /* words */
     l, /* lines */
     t, /* this line */
     L, /* longest line */
     c, /* current character */
     s; /* s==1 if the current word has been counted */
int main(void) {
  for (; c = getchar()+1; ++b)
       t -= (c==11 ? (l++, (t>L ? L=t : t))
                   : -1),
       s = (c>33 ? w += !s
                 : 0);
  printf("%d %d %d %d\n", l, (t>L ? t : L), w, b);
  return 0;
}

```
> 1 votes

# Answer
# R, 91 characters

**Golfed**

```
x=scan(w="c",se="\n");n=nchar(x);sum(n);length(x);max(n);sum(sapply(strsplit(x," "),length))

```

**Ungolfed**

```
x=scan(what="c",sep="\n")
n=nchar(x)
num.char=sum(n)
num.lines=length(x)
max.line.length=max(n)
word.count=sum(sapply(strsplit(x," "),length))

```

**Output**

```
> x=scan(what="c",sep="\n");n=nchar(x);sum(n);length(x);max(n);sum(sapply(strsplit(x," "),length))
1: This is a test
2: of how well
3: the program works!
4:
Read 3 items
[1] 43
[1] 3
[1] 18
[1] 10

```

**Alternatives**

```
x=scan(w="c",se="\n");n=nchar(x);sum(n);length(x);max(n);length(unlist(gregexpr("\\w+",x)))

```

Saves a character at the expense of not really matching everything.
> 1 votes

# Answer
## Javscript (runs in Rhino) - 213 chars

The java file i/o calls take up a lot of space. But I didn't realize you call java so easily from javascript and thought that was pretty neat:

```
var r=new BufferedReader(new FileReader(f));var s=true;var n=0,l=0,m=0,w=0;while(s){s=r.readLine();if(s){n+=s.length();l+=1;m=m<s.length()?s.length():m;w+=s.split("\\s+").length;}}print(n+','+n+','+l+','+m+','+w);

```

### Ungolfed:

```
        var reader = new BufferedReader( new FileReader(filename) );
        var s = true;
        var n=0,l=0,m=0,w=0;

        while (s) {
            s = reader.readLine();
            if (s) {
                n+=s.length();
                l+=1;
                m = m<s.length()?s.length():m;
                w += s.split("\\s+").length;
            }
        }
        System.out.println('bytes/chars: '+n+', Lines: '+l+', Max Line: '+m+', Words: '+w);

```
> 0 votes

# Answer
**Python 160**

Your file name is assigned to variable q.

```
g=len
z=open(q,'r')
w=z.read()
z.close()
b,e,f=g(w),g(w.replace('\n',' ').split()),w.split('\n')
d,c,a=g(max(f)),g(f),g(open(q,'rb').read())
for i in 'abcde':
     print eval(i)

```

This prints the 5 requirements in order:

bytes read
characters read
lines read
max line length
words read

(TyrantWaves suggestion implemented)
> 0 votes

# Answer
# K, 40

```
{a:0:x;(#a;+/b;max b:#:'a;+/#:'" "\:'a)}

```

Prints linecount, char count, max line length, word count.

Words are space-separated.
> 0 votes

# Answer
## Python, 98

```
l=len
f=open(q).read()
j=f.split("\n")
for i in (l(f),l(f),l(j),max(j,key=l),l(f.split())):print i

```

98 is including newlines. Do newlines count?
> 0 votes

# Answer
## PHP, 163

```
<?$f=file($argv[1]);$l=0;foreach($f as$i)$l=$l<strlen($i)?strlen($i):$l;$n=count($f);$c=strlen($g=implode($f));$w=count(explode(' ',$g))+$n-1;echo"$c $c $n $l $w";

```
> 0 votes

---
Tags: code-golf
---


title: Detect loops in a linked list

text:
# Question
Title: Detect loops in a linked list
This comes from one of my favorite interview questions, though apparently it is now a fairly well-known puzzle. I have no way of knowing, but if you have already heard the answer it would be polite to let others try instead.

### Task:

Write a function that takes as input a singly-linked list and returns true if it loops back on itself, and false if it terminates somewhere.

Here's some example code in C as a starting point so you can see what I mean, but feel free to write your answer in whatever language you like:

```
struct node
{
    void *value;
    struct node *next;
};

int has_loops(struct node *first)
{
    /* write your own loop detection here */
}

```

### Hints:

There is a way to make this function run in O(n) time with a constant amount of extra memory. Good on you if you figure it out, but any working answer deserves some upvotes in my book.

# Answer
## C, non-golfed

The idea is to have to pointers p1 and p2 that traverse the list. p2 moves twice as fast as p1. If p2 reaches p1 at some point then there is a loop. Here is the C code (not tested, though).

```
struct node
{
  void *value;
  struct node *next;
};

int has_loops(struct node *p)
{
  struct node *p1 = p, *p2 = p->next;
  if (!p2) return 0;

  while (p1 != p2) {
    // p1 goes one step
    p1 = p1->next;
    if (!p1) return 0;

    // p2 goes two steps
    p2 = p2->next;
    if (!p2) return 0;
    p2 = p2->next;
    if (!p2) return 0;
  }

  return 1;
}

```
> 6 votes

# Answer
## Ada

The "Floyd's Cycle-Finding Algorithm" is the best solution. It's also called "The Tortoise and the Hare Algorithm".

linked\_lists.ads:

```
generic
   type Element_Type is private;
package Linked_Lists is

   type Node is private;
   type List is private;

   function Has_Loops (L : List) return Boolean;

private

   type List is access Node;
   type Node is record
      Value   : Element_Type;
      Next    : List;
   end record;

end Linked_Lists;

```

linked\_lists.adb:

```
package body Linked_Lists is

   function Has_Loops (L : List) return Boolean is
      Slow_Iterator : List := L;
      Fast_Iterator : List := null;
   begin
      -- if list has a second element, set fast iterator start point
      if L.Next /= null then
         Fast_Iterator := L.Next;
      end if;

      while Fast_Iterator /= null loop

         -- move slow iterator one step
         -- guaranteed to be /= null, since it is behind fast iterator
         Slow_Iterator := Slow_Iterator.Next;

         -- move fast iterator one step
         -- guaranteed to be valid, since while catches null
         Fast_Iterator := Fast_Iterator.Next;
         -- move fast iterator another step
         -- null check necessary
         if Fast_Iterator /= null then
            Fast_Iterator := Fast_Iterator.Next;
         end if;

         -- if fast iterator arrived at slow iterator -> loop detected
         if Fast_Iterator = Slow_Iterator then
            return True;
         end if;

      end loop;

      -- fast iterator arrived end, no loop present.
      return False;
   end Has_Loops;

end Linked_Lists;

```

here is the implementation of the Brent algorithm:

```
package body Linked_Lists is

   function Has_Loops (L : List) return Boolean is
      Turtle : List     := L;
      Rabbit : List     := L;
      Steps  : Natural  := 0;
      Limit  : Positive := 2;
   begin

      -- is rabbit at end?
      while Rabbit /= null loop

         -- increment rabbit
         Rabbit := Rabbit.Next;
         -- increment step counter
         Steps := Steps + 1;

         -- did rabbit meet turtle?
         if Turtle = Rabbit then
            -- LOOP!
            return True;
         end if;

         -- is it time to move turtle?
         if Steps = Limit then
            Steps := 0;
            Limit := Limit * 2;
            -- teleport the turtle
            Turtle := Rabbit;
         end if;

      end loop;

      -- rabbit has reached the end
      return False;
   end Has_Loops;

end Linked_Lists;

```
> 2 votes

# Answer
Since the solution is already in the open, I think it's fair to step in now with Brent's algorithm, which is the one I'm familiar with from integer factorisation.

```
#define bool int
#define false 0
#define true 1

bool has_loops(struct node *first) {
    if (!first) return false;

    struct node *a = first, *b = first;
    int step = 1;

    while (true) {
        for (int i = 0; i < step; i++) {
            b = b->next;
            if (!b) return false;
            if (a == b) return true;
        }

        a = a->next;
        if ((step << 1) > 0) step <<= 1;
    }
}

```
> 2 votes

# Answer
## Haskell

Naive algorithm:

```
import Data.Set (Set)
import qualified Data.Set as Set

type Id = Integer
data Node a = Node { getValue :: a, getId :: Id }

hasLoop :: [Node a] -> Bool
hasLoop = hasLoop' Set.empty

hasLoop' :: Set Id => [Node a] -> Bool
hasLoop' set xs = case ns of
  [] -> False
  x:xs' -> let
    ident = getId x
    set' = Set.insert ident set
    in if Set.member ident set
      then True
      else hasLoop' set' xs'

```

Floyd's Cycle-Finding Algorithm:

```
import Control.Monad (join)
import Control.Monad.Instances ()
import Data.Function (on)
import Data.Maybe (listToMaybe)

type Id = Integer
data Node a = Node { getValue :: a, getId :: Id }

next :: [a] -> Maybe [a]
next [] = Nothing
next (_:xs) = Just xs

nexts :: [a] -> [a] -> (Maybe [a], Maybe [a])
nexts xs ys = (next xs, next $ next ys)

hasLoop :: [Node a] -> Bool
hasLoop = uncurry hasLoops' . join nexts

hasLoop' :: Maybe [Node a] -> Maybe [Node a] -> Bool
hasLoop' (Just xs) (Just ys)
  | on (==) (getId . listToMaybe) xs ys = True
  | otherwise = uncurry hasLoop' $ nexts xs ys
hasLoop' _ Nothing = False
hasLoop' Nothing _ = False -- not needed, but there for case completeness

```
> 0 votes

# Answer
# D

This is a solution I thought of myself. It runs in O(n) and uses O(1) memory.

What I'm doing is simply iterating through the list and reversing all the pointers. If the list contains a cycle, you'll eventually end up at the beginning of the list and otherwise you end up at the end, which is somewhere else if your list is longer than 1. Now you've determined the result you can restore the list by simply reversing the pointers again.

Here is my code and a test:

```
import std.stdio;

// The list structure.
struct node(T)
{
    T data;
    node!T * next;

    this(T data) {this.data = data; next = null;}
}

bool hasLoop(T)(node!T * first)
{
    // List shorter than two nodes has no loops.
    if(!first || !first.next)
    {
        return false;
    }

    // Keep iterating through the list, while reversing the pointers.
    node!T * previous = null,
             current = first;
    while(current)
    {
        auto next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }

    // If the last node was the beginning of the list, there was a cycle.
    // Otherwise, there are none.
    bool result = previous == first;

    // Do the reversal again to restore the list to its original state.
    current = previous;
    previous = null;
    while(current)
    {
        auto next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }

    // Done!
    return result;
}

// Test
unittest
{
    // Build a list.
    int[] elems = [1,2,3,4,5,6,7,8,42];

    auto list = new node!int(elems[0]);
    auto curr = list;
    foreach(x; elems[1..$])
    {
        curr.next = new node!int(x);
        curr = curr.next;
    }

    // Outcomment the line below to test for a non-cycle list.
    curr.next = list.next.next.next;

    // Do cycle check.
    writeln(hasLoop(list) ? "yes" : "no");

    // Confirm the list is still correct.
    curr = list;
    for(int i = 0; i < elems.length; ++i, curr = curr.next)
    {
        assert(curr.data == elems[i]);
    }
}

```
> 0 votes

---
Tags: code-challenge
---


title: Crossword numbering

text:
# Question
Title: Crossword numbering
Produce a program to correctly number a crossword grid.

## Input

The input will be the name of a file representing the crossword grid. The input filename may be passed as an argument, on the standard input, or by other conventional means other than hardcoding.

**Grid file format:** A text file. The first line consists of two white-space separated integer constants `M` and `N`. Following that line are `M` lines each consisting of `N` characters (plus a new line) selected from `[#A-Z ]`. These characters are interpreted such that `'#'` indicates a blocked square, `' '` a open square in the puzzle with no known contents and any letter an open square whose containing that letter.

## Output

The output will be a numbering file, and may be sent to the standard output, to a file whose name is derived from the input filename, to a user specified file, or to some other conventional destination.

**Numbering file format** A text file. Lines starting with '#' are ignored and may be used for comments. All other lines contain a tab separated triplet `i`, `m`, `n` where `i` represents a number to be printed on the grid, and `m` and `n` represent the row and column of the square where it should be printed. The number of both rows and columns starts at 1.

## Numbering scheme

A correctly numbered grid has the following properties:

1. Numbering begins at 1.
2. No column or span of open squares is unnumbered. (You may assume that no single character answer will exist in the problem.)
3. Numbers will be encountered in counting order by scanning from top row to the bottom taking each row from left to right. (So, every horizontal span is numbered at its leftmost square, and every column is numbered at its topmost square.)

## Test input and expected output

Input:

```
5   5
#  ##
#
  #
    #
##  #

```

Output (neglecting comment lines):

```
1       1       2
2       1       3
3       2       2
4       2       4
5       2       5
6       3       1
7       3       4
8       4       1
9       4       3
10      5       3

```

## Aside

This is the first of what will hopefully be several crossword related challenges. I plan to use a consistent set of file-formats throughout and to build up a respectable suite of crossword related utilities in the process. For instance a subsequent puzzle will call for printing a ASCII version of the crossword based on the input and output of this puzzle.

# Answer
> 4 votes
# Ruby - ~~210~~ 139 characters

```
o=0
(n=(/#/=~d=$<.read.gsub("
",S='#'))+1).upto(d.size-1){|i|d[i]!=S&&(i<n*2||d[i-1]==S||d[i-n]==S)&&print("%d\t%d\t%d
"%[o+=1,i/n,i%n+1])}

```

Tested with ruby 1.9.

# Answer
> 3 votes
## Python, 194 177 176 172 characters

```
f=open(raw_input())
V,H=map(int,next(f).split())
p=W=H+2
h='#'
t=W*h+h
n=1
for c in h.join(f):
 t=t[1:]+c;p+=1
 if'# 'in(t[-2:],t[::W]):print"%d\t%d\t%d"%(n,p/W,p%W);n+=1

```

# Answer
> 3 votes
# PHP - 175 characters

```
<?for($i=$n=strpos($d=strtr(`cat $argv[1]`,"\n",$_="#"),$_)+$o=1;isset($d[$i]);++$i)$d[$i]!=$_&($i<$n*2|$d[$i-1]==$_|$d[$i-$n]==$_)&&printf("%d\t%d\t%d\n",$o++,$i/$n,$i%$n+1);

```

# Answer
> 2 votes
### C++ 270 264 260 256 253 char

```
#include<string>
#include<iostream>
#define X cin.getline(&l[1],C+2)
using namespace std;int main(){int r=0,c,R,C,a=0;cin>>R>>C;string l(C+2,35),o(l);X;for(;++r<=R;o=l)for(X,c=0;++c<=C;)if(l[c]!=35&&(l[c-1]==35||o[c]==35))printf("%d %d %d\n",++a,r,c);}

```

To use:

```
g++ cross.cpp -o cross
cat puzzle |  cross

```

Nicely formatted:

```
#include<string>
#include<iostream>
// using this #define saved 1 char
#define X cin.getline(&l[1],C+2)

using namespace std;

int main()
{
    int r=0,c,R,C,a=0;
    cin>>R>>C;
    string l(C+2,35),o(l);
    X;

    for(;++r<=R;o=l)
        for(X,c=0;++c<=C;)
            if(l[c]!=35&&(l[c-1]==35||o[c]==35))
                printf("%d %d %d\n",++a,r,c);
}

```

I tried reading the whole crossword in one go and using a single loop.
But the cost of compensating for the '\n character outweighed any gains:

```
#include <iostream>
#include <string>
#define M cin.getline(&l[C+1],R*C
using namespace std;

int main()
{
    int R,C,a=0,x=0;
    cin>>R>>C;
    string l(++R*++C,35);
    M);M,0);

    for(;++x<R*C;)
        if ((l[x]+=l[x]==10?25:0)!=35&&(l[x-1]==35||l[x-C]==35))
            printf("%d %d %d\n",++a,x/C,x%C);
}

```

Compressed: 260 chars

```
#include<iostream>
#include<string>
#define M cin.getline(&l[C+1],R*C
using namespace std;int main(){int R,C,a=0,x=0;cin>>R>>C;string l(++R*++C,35);M);M,0);for(;++x<R*C;)if((l[x]+=l[x]==10?25:0)!=35&&(l[x-1]==35||l[x-C]==35))printf("%d %d %d\n",++a,x/C,x%C);}

```

# Answer
> 2 votes
## C, 184 189 chars

```
char*f,g[999],*r=g;i,j,n;main(w){
for(fscanf(f=fopen(gets(g),"r"),"%*d%d%*[\n]",&w);fgets(r,99,f);++j)
for(i=0;i++<w;++r)
*r==35||j&&i>1&&r[-w]-35&&r[-1]-35||printf("%d\t%d\t%d\n",++n,j+1,i);}

```

Not much to say here; the logic is pretty basic. The program takes the filename on standard input at runtime. (It's so annoying that the program has to work with a filename, and can't just read the file contents directly from standard input. But the one who pays the piper calls the tune!)

The weird `fscanf()` pattern is my attempt to scan the full first line, including the newline but **not** including leading whitespace on the following line. There's a reason why nobody uses `scanf()`.

# Answer
> 1 votes
## Reference implementation:

**c99** ungolfed and rather more than 2000 characters including various debugging frobs still in there.

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

void printgrid(int m, int n, char grid[m][n]){
  fprintf(stderr,"===\n");
  for (int i=0; i<m; ++i){
    for (int j=0; j<n; ++j){
      switch (grid[i][j]) {
      case '\t': fputc('t',stderr); break;
      case '\0': fputc('0',stderr); break;
      case '\n': fputc('n',stderr); break;
      default: fputc(grid[i][j],stderr); break;
      }
    }
    fputc('\n',stderr);
  }
  fprintf(stderr,"===\n");
}

void readgrid(FILE *f, int m, int n, char grid[m][n]){
  int i = 0;
  int j = 0;
  int c = 0;
  while ( (c = fgetc(f)) != EOF) {
    if (c == '\n') {
      if (j != n) fprintf(stderr,"Short input line (%d)\n",i);
      i++;
      j=0;
    } else {
      grid[i][j++] = c;
    }
  }
}

int main(int argc, char** argv){
  const char *infname;
  FILE *inf=NULL;
  FILE *outf=stdout;

  /* deal with the command line */
  switch (argc) {
  case 3: /* two or more arguments. Take the second to be the output
         filename */
    if (!(outf = fopen(argv[2],"w"))) {
      fprintf(stderr,"%s: Couldn't open file '%s'. Exiting.",
          argv[0],argv[2]);
      return 2;
    }
    /* FALLTHROUGH */
  case 2: /* exactly one argument */
    infname = argv[1];
    if (!(inf = fopen(infname,"r"))) {
      fprintf(stderr,"%s: Couldn't open file '%s'. Exiting.",
          argv[0],argv[1]);
      return 1;
    };
    break;
  default:
    printf("%s: Number a crossword grid.\n\t%s <grid file> [<output file>]\n",
       argv[0],argv[0]);
    return 0;
  }

  /* Read the grid size from the first line */
  int m=0,n=0;
  char lbuf[81];
  fgets(lbuf,81,inf);
  sscanf(lbuf,"%d %d",&m,&n);

  /* Intialize the grid */
  char grid[m][n];
  for(int i=0; i<m; ++i) {
    for(int j=0; j<n; ++j) {
      grid[i][j]='#';
    }
  }

/*    printgrid(m,n,grid); */
  readgrid(inf,m,n,grid);
/*    printgrid(m,n,grid);  */

  /* loop through the grid  produce numbering output */
  fprintf(outf,"# Numbering for '%s'\n",infname);
  int num=1;
  for (int i=0; i<m; ++i){
    for (int j=0; j<n; ++j){
/*       fprintf(stderr,"\t\t\t (%d,%d): '%c' ['%c','%c']\n",i,j, */
/*        grid[i][j],grid[i-1][j],grid[i][j-1]); */
      if ( grid[i][j] != '#' &&
       ( (i == 0) || (j == 0) ||
         (grid[i-1][j] == '#') ||
         (grid[i][j-1] == '#') )
         ){
    fprintf(outf,"%d\t%d\t%d\n",num++,i+1,j+1);
      }
    }
  }
  fclose(outf);
  return 0;
}

```

# Answer
> 1 votes
**PerlTeX**: 1143 chars (but I haven't golfed it yet)

```
\documentclass{article}

\usepackage{perltex}
\usepackage{tikz}

\perlnewcommand{\readfile}[1]{
  open my $fh, '<', shift;
  ($rm,$cm) = split /\s+/, scalar <$fh>;
  @m = map { chomp; [ map { /\s/ ? 1 : 0 } split // ] } <$fh>;
  return "";
}

\perldo{
  $n=1;
  sub num {
    my ($r,$c) = @_;
    if ($r == 0) {
      return $n++;
    }
    if ($c == 0) {
      return $n++;
    }
    unless ($m[$r][$c-1] and $m[$r-1][$c]) {
      return $n++;
    }
    return;
  }
}

\perlnewcommand{\makegrid}[0]{
  my $scale = 1;
  my $return;
  my ($x,$y) = (0,$r*$scale);
  my ($ri,$ci) = (0,0);
  for my $r (@m) {
    for my $open (@$r) {
      my $f = $open ? '' : '[fill]';
      my $xx = $x + $scale;
      my $yy = $y + $scale;
      $return .= "\\draw $f ($x,$y) rectangle ($xx,$yy);\n";

      my $num = $open ? num($ri,$ci) : 0;
      if ( $num ) {
        $return .= "\\node [below right] at ($x, $yy) {$num};";
      }

      $x += $scale;
      $ci++;
    }
    $ci = 0;
    $x = 0;
    $ri++;
    $y -= $scale;
  }
  return $return;
}

\begin{document}
\readfile{grid.txt}

\begin{tikzpicture}
  \makegrid
\end{tikzpicture}

\end{document}

```

It needs a file called `grid.txt` with the spec, then compile with

```
perltex --nosafe --latex=pdflatex grid.tex

```

# Answer
> 1 votes
### Scala 252:

```
object c extends App{val z=readLine.split("[ ]+")map(_.toInt-1)
val b=(0 to z(0)).map{r=>readLine}
var c=0
(0 to z(0)).map{y=>(0 to z(1)).map{x=>if(b(y)(x)==' '&&((x==0||b(y)(x-1)==35)||(y==0||b(y-1)(x)==35))){c+=1
println(c+"\t"+(y+1)+"\t"+(x+1))}}
}}

```

compilation and invocation:

```
scalac cg-318-crossword.scala && cat cg-318-crossword | scala c

```

# Answer
> 0 votes
**SHELL SCRIPT**

```
#!/bin/sh
crossWordFile=$1

totLines=`head -1 $crossWordFile | cut -d" " -f1`
totChars=`head -1 $crossWordFile | awk -F' ' '{printf $2}'`

NEXT_NUM=1
for ((ROW=2; ROW<=(${totLines}+1); ROW++))
do
   LINE=`sed -n ${ROW}p $crossWordFile`
   for ((COUNT=0; COUNT<${totChars}; COUNT++))
   do
      lineNumber=`expr $ROW - 1`
      columnNumber=`expr $COUNT + 1`
      TOKEN=${LINE:$COUNT:1}
      if [ "${TOKEN}" != "#" ]; then
      if [ ${lineNumber} -eq 1 ] || [ ${columnNumber} -eq 1 ]; then
          printf "${NEXT_NUM}\t${lineNumber}\t${columnNumber}\n"
          NEXT_NUM=`expr $NEXT_NUM + 1`
      elif [ "${TOKEN}" != "#" ] ; then
          upGrid=`sed -n ${lineNumber}p $crossWordFile | cut -c"${columnNumber}"`
          leftGrid=`sed -n ${ROW}p $crossWordFile | cut -c${COUNT}`
          if [ "${leftGrid}" = "#" ] || [ "${upGrid}" = "#" ]; then
          printf "${NEXT_NUM}\t${lineNumber}\t${columnNumber}\n"
          NEXT_NUM=`expr $NEXT_NUM + 1`
          fi
      fi
      fi
   done
done

```

sample I/O:

./numberCrossWord.sh crosswordGrid.txt

```
1       1       2
2       1       3
3       2       2
4       2       4
5       2       5
6       3       1
7       3       4
8       4       1
9       4       3
10      5       3

```

# Answer
> 0 votes
**ANSI C 694 chars**

This is a C version that looks for horizontal or vertical runs of two spaces that are either butted up against the edge, or against a '#' character.

Input file is taken from stdin and must be:

```
<rows count> <cols count><newline>
<cols characters><newline> x rows
...

```

Any tips for compacting this will be gratefully received.

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

#define H '#'

char *p,*g;
int m=0,d=0,r=0,c=0,R=0,C=0;
void n() {
    while(!isdigit(d=getchar()));
    m=d-'0';
    while(isdigit(d=getchar()))
        m=m*10+d-'0';
}

int t() {
    return (((c<1||*(p-1)==H)&&c<C-1&&*p!=H&&p[1]!=H)||
            ((r<1||*(p-C-1)==H)&&r<R-1&&*p!=H&&p[C+1]!=H));
}

int main (int argc, const char * argv[])
{
    n();R=m;m=0;n();C=m;
    p=g=malloc(R*C+R+1);
    while((d=getchar())!=EOF) {
        *p++=d;
    }
    int *a,*b;
    b=a=malloc(sizeof(int)*R*C+R+1);
    p=g;m=0;
    while(*p) {
        if(t()) {
            *a++=++m;
            *a++=r+1;
            *a++=c+1;
        }
        if(++c/C) r++,p++;
        c-=c/C*c;
        p++;
    }
    while(*b) {
        printf("%d\t%d\t%d\n",*b,b[1],b[2]);
        b+=3;
    }
}

```

Output for the Example Provided

```
1   1   2
2   1   3
3   2   2
4   2   4
5   2   5
6   3   1
7   3   4
8   4   1
9   4   3
10  5   3

```

---
Tags: code-golf, crossword
---


title: Text-Twist - similar to boggle problem

text:
# Question
Title: Text-Twist - similar to boggle problem
A similar play on the boggle problem from before (some text from that has been used below, edited to fit) any code that solves the familiar "text-twist" game

### Objective

7 letters are given at random, to which there is a minimum 1 word that uses all 7 letters, and multiple words using less (3 or more required)

The letters may be used in any order, however not duplicated (unless duplicates are included in the 7)

Your code should run for no more than 1 minute (60 seconds). At that time, it should have solved all results.

Final challenge score will be the character count of the program. In the event of a tie, the winner will be the fastest output, decided by an average of 3 inputs, the same being given to both. In the event there is still a tie, the winner will be whichever algorithm found more long (6+) words.

### Rules / constraints

Please refer to wordlist.sourceforge.net for a word list (use ISPELL "english.0" list - the SCOWL list is missing some pretty common words). This listing may be referenced in your code any way you wish.

# Answer
## Perl, 90 chars

```
$_++for@q{<>=~/./g};open E,"E";while(<E>){%p=%q;$.*=$p{$_}--for/./g;y///c>3&&$.&&print}

```

The program takes the list of letters as a line on standard input. The word list is referenced as a file in the current directory named "E". (Presumably this falls under the umbrella of "any way you wish".)

Some other assumptions I made that were not spelled out in the problem description:

* that the goal was to produce a program (as opposed to a function);
* that the input was case-sensitive;
* that apostrophes and hyphens were not to be ignored;
* that the program was required to not match on words in the word list that were too short.

Also, I wonder if the time limit given in the original description is necessary. Even when given a huge list of letters such that every word in "english.0" matches, my program still runs to completion in under 1s.
> 5 votes

# Answer
### Ruby ~~154 152~~ 151

```
require 'set'
d=Set.new(File.read(?e).split)
(3..7).each{|t|puts (0..6).to_a.permutation(t).map{|p|p.map{|i|$*[0][i]}.join}.select{|w|d.include? w}|[]}

```

Expects the 7 letter input as the first command line argument (ex: `ruby texttwist.rb abcdefg`). Dictionary is in a file called "e" in the same dir.
> 2 votes

# Answer
## Python, 158 chars

```
w=raw_input()
q=dict.fromkeys(w,0)
for c in w:q[c]+=1
for b in open('E'):
 p=dict(q)
 for c in b[:-1]:
    if p.get(c,0):p[c]-=1
    else:b=''
 if len(b)>3:print b,

```

This seems larger than it needs to be, but I'm just starting to learn Python from a golfing perspective. Hopefully someone more Python-savvy will submit a better answer.
> 2 votes

# Answer
# bash 152

```
s(){
echo $1|sed -r 's/(.)/\1\n/g'|sort|tr -d "\n"
}
o=`s $1|sed -r 's/(.)/\1?/g'`
for s in `egrep "^[$1]{3,7}$" e`;do s $s|egrep -q ^$o$&& echo $s;done

```

The file has to be renamed to 'e' (line 1) to make it work.

Ungolfed:

Let's generate the testdata ourself:

```
alpha=({a..z})
word=$(for n in {1..7}; do r=$((RANDOM%26)); echo -n ${alpha[r]}; done ; echo)
echo $word
# $word=owimvhl

```

In above code, $word is $1 - user input.

```
text=$(egrep "^[$word]{3,7}$" english.0)
# t=hill him hollow how howl iii ill loom low mill mom mow oil owl vii viii vow whim who whom will willow woo wool

```

We take every word of len 3 to 7 from the english.0 dict, ^...$ prevent unwanted characters to slip in. We still might have unwanted duplicates, however.

```
sort () {
  echo $w | sed -r 's/(.)/\1\n/g' | sort | tr -d '\n'
}
# sort $w7 => hilmovw

```

We now split the word, to sort the characters, and rebuild the word. Now we insert a ? after every character:

```
optional=$(sort $word|sed -r 's/(.)/\1?/g')
# h?i?l?m?o?v?w?

```

This way we only use every character, which appears only once, only once.

```
for s in $text ; do sort $s | egrep -q "^$optional$" && echo $s; done
him
how
howl
low
mow
oil
owl
vow
whim
who
whom

```

Hm. Assertion that there is a match with 7 characters didn't hold. Try something else:

```
time ./cg-5947-text-twist.sh unknown
know
known
non
noun
now
nun
own
unknown

real    0m0.207s
user    0m0.200s
sys 0m0.052s

```
> 2 votes

# Answer
### C# 412

```
void F(string l){
for(var i=3;i<8;i++)
foreach(var s in P(l.Length,i,new int[]{})
.Select(p=>new string(p.Select(c=>l[c]).ToArray()))
.Where(File.ReadAllLines("e").Contains)
.Distinct())
Console.WriteLine(s);
}
IEnumerable<int[]>P(int n,int r,int[]c){
if(c.Length<r)
for(var i=0;i<n;i++)foreach(var j in P(n,r,c.Concat(new[]{i}).ToArray()))yield return j;
else
if(c.Length==c.Distinct().Count())yield return c;
}

```

Not really the right language to golf in, but it was fun. :)

The entry point is the `F` method, which needs to be called with a `string` argument representing the 7 letters.

I tested it with the input `"indents"` got this output: http://pastebin.com/uBuwr50R (unfortunately I don't think it's possible to run this on ideone.com because of the dictionary file dependency).

The above test executes in about 7.5s on my machine.

If I replace `File.ReadAllLines("e")` with `new HashSet<string>(File.ReadAllLines("e"))`, the execution time drops to about 1.5s, but at a pretty high character count cost.

Just like breadbox (in his Perl answer), I:

* named the dictionary file `e` and considered it's present in the current dir
* made the string comparisons case sensitive
* did not ignore special characters (apostrophes, hyphens) in string comparisons

*Update:* Here's an ungolfed (and slightly refactored for readability) version: http://pastebin.com/b1wxv4zU
> 1 votes

---
Tags: code-golf
---