# Question
Title: Write a java code to detect the JVM version
The objective is to write java code that detects the JVM version relying in compatibility changes, side effects, bugs and/or undefined behavior that works in a way in one version and another way in another version. Further, the code should be at least a bit readable, without sacrificing whitespaces and legible variable names.

To ensure that objective, the exact formal rules are:

1. The code must be written in java and should output the JRE version in which it is running.
2. The code must not use any JDK or JRE API provided specifically for detecting the java version or which gives the JDK or JRE version for free.
3. The code must not use reflection.
4. The code is only required to work in Hotspot Java SE 5, 6 and 7, but may work in other JVMs.
5. The code must not use any third-party libraries in the classpath.
6. The code must not start any other process, java or not.
7. The code must not use environment variables.
8. The code must not search the file system looking for pre-existing files or folders.
9. The code must be contained in a single file and be called via `public static void main(String[] args)` or `public static void main(String... args)`.
10. The code must not use any non-public API present in the JRE.
11. The code must not generate any NoClassDefFoundError, NoSuchMethodError, ClassNotFoundException or NoSuchMethodException during its execution.
12. The code should run in a system disconnected from the internet or from any local network.
13. You should provide an explanation of why it behaves in one way in a version and another way in another version.

# Scoring

The method used for measuring the best solution is max(n/s), where n is the number of different java versions detected without violating any of these rules (at least versions 5, 6 and 7) and s is the number of lexical tokens in the solution.

# Answer
> 9 votes
# 6/102 = 0.0588

Detects 6 versions. Has 102 lexical tokens (down from 103, after I deleted `public` in `public class`).

```
import java.security.Signature;

class GuessVersion {
        public static void main(String[] args) {
                String version = "Java 1.1";
                try {
                        "".getBytes("ISO8859_13");
                        version = "Java 1.3";

                        "".getBytes("ISO8859_15");
                        version = "Java 1.4";

                        Signature.getInstance("SHA256withRSA");
                        version = "Java 5";

                        "".getBytes("KOI8_U");
                        version = "Java 6";

                        Signature.getInstance("SHA256withECDSA");
                        version = "Java 7";
                } catch(Exception e) {}
                System.out.println(version);
        }
}

```

Java 1.1 introduced character encodings and cryptographic algorithms to Java. Later versions added more encodings and algorithms. This program tries to use encodings and algorithms until it catches an exception. I expect a missing encoding to throw `java.io.UnsupportedEncodingException` and a missing algorithm to throw `java.security.NoSuchAlgorithmException`.

I had an old PowerPC Macintosh with four old versions of Java. My OpenBSD machine has two more versions, so I tested these six versions:

* Java 1.1.8 in MRJ 2.2.6 for Mac OS 9.2.2
* Java 1.3.1\_16 for Mac OS X Panther
* Java 1.4.2\_21 for Mac OS X Tiger
* Java 1.5.0\_19 for Mac OS X Tiger
* OpenJDK 1.6.0\_32 for OpenBSD 5.5
* OpenJDK 1.7.0\_21 for OpenBSD 5.5

This program can also run in JamVM 1.5.4 and gcj 4.8.2 for OpenBSD, but does not identify them as different implementations. It only prints "Java 5".

## Mac OS Runtime for Java

Thanks to "Write once, run everywhere!", I may write this program once, compile it once, and run one GuessVersion.class in all eight virtual machines. I need a compiler for Java 1.1, the oldest version in my collection.

My compiler is the `javac` tool from MRJ SDK 2.2. Because the Classic Mac OS had no command line, `javac` is a pretty graphical tool where I select files and options and click "Do Javac". After I edit my code, I just click "Do Javac" again.

The easiest way to run GuessVersion.class is to open it in JBindery, another tool from MRJ SDK 2.2. The runtime is MRJ 2.2.6, an implementation of Java 1.1.8.

# Answer
> 22 votes
I'm not sure what my score is, because it depends on what precisely you consider to be a lexical token, but I'm trying to abuse that counting system as much as possible with a long string...

It also depends on whether you count this as identifying 7 different versions or 16... (It could trivially be extended up to 190).

```
class V extends ClassLoader
{
    public static void main(String[]args)
    {
        for(byte b=60;;)
            try {
                byte[]buf="\u00ca\u00fe\u00ba\u00be\u0000\u0000\u00002\u0000\u0005\u0007\u0000\u0003\u0007\u0000\u0004\u0001\u0000\u0001A\u0001\u0000\u0010java/lang/Object\u0006\u0000\u0000\u0001\u0000\u0002\u0000\u0000\u0000\u0000\u0000\u0000\u0000\u0000".getBytes("ISO-8859-1");
                buf[7]=b--;
                new V().defineClass(buf,0,53);
                System.out.println(b-43);
                break;
            }
            catch(Throwable t){}
    }
}

```

It works by attempting to define an interface in a custom classloader with descending major version numbers of the class format. The first one which doesn't throw a `java.lang.UnsupportedClassVersionError` corresponds to the VM's version.

# Answer
> 8 votes
```
class Evil {
    public static void main(String... args) {
        String s1 = "Good";
        s1 += "morning";
        int a = 7;
        if (s1 != s1.intern())
            try {
                a--;
                javax.xml.datatype.DatatypeFactory.newInstance().newXMLGregorianCalendar().equals(null);
            } catch (Throwable e) {
                a--;
            }
        System.out.println(a);
    }
}

```

The interning algorithm changed between Java 6 and 7. See https://stackoverflow.com/a/7224864/540552

XMLGregorianCalendar.equals(null) used to throw NullPointerException in java 5, but this was fixed in java 6. See https://bugs.java.com/bugdatabase/view\_bug?bug\_id=6285370

100 96 92 87 85 tokens here. Thanks to Peter Taylor for reducing 7 tokens.

---
Tags: code-challenge, java
---


title: Polygon prefixes

text:
# Question
Title: Polygon prefixes
Polygons are named after the number of sides that they have. A pentagon has 5 sides, an octagon has 8 sides. But how are they named? What's the name for a 248-sided polygon?

All polygons are suffixed with `-gon`. There are specific prefixes for each polygon depending on the number of sides. Here are the prefixes for the lower numbers:

```
3 - tri
4 - tetra
5 - penta
6 - hexa
7 - hepta
8 - octa
9 - nona
10 - deca
11 - undeca
12 - dodeca
13 - triskaideca
14 - tetradeca
15 - pentadeca
16 - hexadeca
17 - heptadeca
18 - octadeca
19 - nonadeca
20 - icosa

```

Polygons with 21 to 99 sides have a different system. Take the prefix for the tens digit (found on the left column), the ones digit (right column below), and then stick a "kai" between them to get `(tens)kai(ones)gon`.

```
10 - deca        | 1 - hena
20 - icosi       | 2 - di
30 - triaconta   | 3 - tri
40 - tetraconta  | 4 - tetra
50 - pentaconta  | 5 - penta
60 - hexaconta   | 6 - hexa
70 - heptaconta  | 7 - hepta
80 - octaconta   | 8 - octa
90 - nonaconta   | 9 - nona

```

The 3-digit sided polygons are named in a similar fashion. A 100-sided polygon is called a hectogon. Take the hundreds digit, find it on the column for ones digits, then stick a "hecta" to its right. Now number off the tens and ones like above: `(hundreds)hecta(tens)kai(ones)gon`. If the hundreds place digit is a 1, don't put the prefix behind "hecta"; if the ones place is 0, then omit the (ones) section.

So, given an integer (3 \<= n \<= 999), return the name of an n-sided polygon. `n-gon` is not a valid answer :P

As with all code golf, shortest code wins.

# Answer
## C, 401, 391

Lets put something out there so there is at least one answer for reference :-)

```
char*s[]={"","hena","di","tri","tetra","penta","hexa","hepta","octa","nona","un","do","triskai","deca","icosi","tria","conta","kai","icosa","hecto","hecta","gon\n"};
p(i){printf(s[i]);}
t;n(i){
    if(i<10)
        p(i);   // ones
    else if(i<20){
        i-=10;
        p(i+(i&&i<4)*9); // teens
        p(13); // "deca"
    }else if(i==20)
        p(18); // "icosa"
    else if(i==100)
        p(19); // "hecto"
    else{
        t=i/100;
        p(t>1?t:0); // hundreds
        p(t?20:0);  // "hecta"
        i%=100;
        t=i/10;
        p(t+(t&&t<4)*12); // tens
        p(t>2?16:0);      // "conta"
        i%=10;
        p(i?17:0); // "kai"
        p(i);      // ones
    }
    p(21); // "gon\n"
}

```

Test with:

```
main(){
    for(int i=3;i<=999;i++){
        printf("%3d: ",i);n(i);
    }
}

```

Subset of output:

```
  3: trigon
  4: tetragon
  5: pentagon
  6: hexagon
  7: heptagon
  8: octagon
  9: nonagon
 10: decagon
 11: undecagon
 12: dodecagon
 13: triskaidecagon
 14: tetradecagon
 15: pentadecagon
 16: hexadecagon
 17: heptadecagon
 18: octadecagon
 19: nonadecagon
 20: icosagon
 21: icosikaihenagon
 22: icosikaidigon
 23: icosikaitrigon
...
 99: nonacontakainonagon
100: hectogon
101: hectakaihenagon
102: hectakaidigon
103: hectakaitrigon
104: hectakaitetragon
105: hectakaipentagon
106: hectakaihexagon
107: hectakaiheptagon
108: hectakaioctagon
109: hectakainonagon
110: hectadecagon
111: hectadecakaihenagon
...
997: nonahectanonacontakaiheptagon
998: nonahectanonacontakaioctagon
999: nonahectanonacontakainonagon

```
> 5 votes

# Answer
## JavaScript -  405  386

Version 1: (405 chars)

```
i=prompt(),o='0hena0di0tri0tetra0penta0hexa0hepta0octa0nona'.split(0),d='0W0icosi0triaQ0tetraQ0pentaQ0hexaQ0heptaQ0octaQ0nonaQ'.split(0),t='W0unW0doW0triskaiW0tetraW0pentaW0hexaW0heptaW0octaW0nonaW0icosa'.split(0),x=('000'+i).substr(-3).split('');alert((i<10?o[i]:i<21?t[i-10]:i==100?'hecto':(i<100?'':i<200?'hecta':o[x[0]]+'hecta')+d[x[1]]+'kai'+o[x[2]]).replace(/Q/g,'conta').replace(/W/g,'deca')+'gon')

```

Version 2: (386 chars)

```
i=prompt(),p='0tetra0penta0hexa0hepta0octa0nona',o='0hena0di0tri'+p,t=('W0unW0doW0triskai'+p.replace(/0/g,'W0')+'W0icosa').split(0),x=('000'+i).substr(-3).split(''),o=o.split(0);alert((i<10?o[i]:i<21?t[i-10]:i==100?'hecto':(i<100?'':i<200?'hecta':o[x[0]]+'hecta')+('0W0icosi0tria'+p.replace(/0/g,'Q0')+'Q').split(0)[x[1]]+'kai'+o[x[2]]).replace(/Q/g,'conta').replace(/W/g,'deca')+'gon')

```

Output example:

```
3: trigon
4: tetragon
5: pentagon
6: hexagon
7: heptagon
8: octagon
9: nonagon
10: decagon
11: undecagon
12: dodecagon
13: triskaidecagon
14: tetradecagon
15: pentadecagon
16: hexadecagon
17: heptadecagon
18: octadecagon
19: nonadecagon
20: icosagon
21: icosikaihenagon
22: icosikaidigon
23: icosikaitrigon
99: nonacontakainonagon
...
100: hectogon
101: hectakaihenagon
102: hectakaidigon
103: hectakaitrigon
104: hectakaitetragon
105: hectakaipentagon
106: hectakaihexagon
107: hectakaiheptagon
108: hectakaioctagon
109: hectakainonagon
110: hectadecakaigon
111: hectadecakaihenagon
...
997: nonahectanonacontakaiheptagon
998: nonahectanonacontakaioctagon
999: nonahectanonacontakainonagon

```
> 1 votes

# Answer
# Cobra - 370 bytes

This is currently a function, but if that isn't allowed then I'll change it.

```
def f(x) as String
    o='. hena di tri tetra penta hexa hepta octa nona'.split
    o[0],t,h,d='',['','deca','icosci','triconta'],['','hecta','dihecta','trihecta'],['undeca','dodeca','triskaideca']
    for z in 4:10,t,h,d=t+[o[z]+'conta'],h+[o[z]+'hecta'],d+[o[z]+'deca']
    for z in 10,t[z]+='kai'
    return if(x-100,h[x//100]+if(10<x<20,d[x-11],t[x%100//10]+o[x%10]),'hecto')+'gon'

```

And for some reason the cobra highlighter has `//` set as a comment, which is wrong.
> 0 votes

---
Tags: code-golf, geometry
---


title: Sum up a number in words

text:
# Question
Title: Sum up a number in words
Here's a simple one.

In the *shortest code possible*, given an arbitrary number such as `567421`, print it out in words:

```
five
six
seven
four
two
one

```

You may assume the input is an integer that is already provided in a one-letter variable such as `n`.

# Answer
> 2 votes
Python

```
for i in `n`:print' ottffssennwhoiieiieoruvxvgn  ere ehe  e   nt'[int(i)::9]

```

"Inspired" by https://codegolf.stackexchange.com/a/32156/18638

---
Tags: code-golf
---


title: Simulate rotating a board

text:
# Question
Title: Simulate rotating a board
# Introduction

You're playing a matching game, in which coins are inserted at the top and fall to the bottom (onto the top coin) due to gravity.

So this

```
O <- inserting this coin

OO O
OOOOO

```

will become this

```
O
OO O
OOOOO

```

Now imagine someone rotates the board clockwise. The following will happen:

### 1. The board is rotated

```
OOO
OO
O
OO
O

```

### 2. Coins fall down due to gravity

```
O
O
OO
OO
OOO

```

# Your task

Your task is to simulate the rotation of the board by writing a program or a function. For the sake of simplicity we're only dealing with one kind of coin (it's not a too exciting matching game, is it…). You can assume that gravity is applied only after the rotation is complete. The board is rotated clockwise.

# Input

The input is going to be a string, which contains 3 types of characters:

* O (capital o) OR 0 (zero) - a coin (you decide which one your solution supports)
* (space) - an empty field
* \n (new line) - end of row

The input represents the state of the board. You can assume, the input is well formed and contains a valid state of the board (no coins are floating). The input can be a function parameter, or can be read from the standard input or from a file.

# Output

The output is the new state of the board after rotation. The output contains the same 3 types of characters as the input. The output can be returned from your function or can be written to the standard output or to a file.

# Sample

Input1:

```
O
OO O
OOOOO

```

Output1:

```
O
O
OO
OO
OOO

```

Input2:

```
O O
O O

```

Output2:

```
OO
OO

```

You can use any language and the standard library of the chosen language. Shortest program in bytes wins.

# Answer
> 16 votes
### GolfScript, 14 12 characters

```
' '-n%zip$n*

```

Input must be given on STDIN, the character for coins can be any non-whitespace characters. Try here. Thanks to Peter for pointing out a two character reduction.

# Answer
> 6 votes
## Ruby 2.0, 59 characters

```
puts$<.map(&:chars).reverse.transpose.sort[1,50].map &:join

```

Input via stdin, assumes lines all have the same length. This is probably much longer than necessary. But at least it's readable ...

# Answer
> 6 votes
# Javascript (E6) 103

First try, just matrix operations. Each row in input string need to be padded.
Quite wordy.

```
R=t=>(x=t.split('\n').reverse().map(x=>[...x].sort()),x.map((c,i)=>x.map(r=>r[i]).join('')).join('\n'))

```

**Pseudo code**

1. string -\> array of rows
2. up/down reverse array
3. each row -\> char array
4. sort each row (coins 'fall' to right)
5. transpose
6. each char array in a row -\> a string
7. join array -\> single string

# Answer
> 3 votes
## J - ~~49~~ ~~31~~ 24 bytes

I think there might be unnecessary rotations in there, but otherwise it works fine. It's a function that takes the input as specified, coins being `O`. No trailing whitespace is required in the input.

New version, inspired by edc65's Javascript answer:

```
f=:[:|."1@|:[:/:~"1,;._2

```

Explanation:

```
f=:[:|."1@|:[:/:~"1,;._2
                   ,;._2 Split the string at every fret, which is the last character in the string (newline).
              /:~"1      Sort every row separately.
     |."1@|:             Rotate the array clockwise.

```

---

Old version:

```
f=:[:|:((#~=&' '),=&'O'#])"1@|:@(|."1@|:)@(,;._2)

```

Explanation:

```
f=:[:|:((#~=&' '),=&'O'#])"1@|:@(|."1@|:)@(,;._2)
                                          (,;._2) Split the string at every fret, which is the last character in the string (newline).
                                (|."1@|:)@        Rotate the array clockwise.
                             |:@                  Reverse the axes (columns become rows and vice-versa).
       ((#~=&' '),=&'O'#])"1                      Function that applies the "gravity"
                          "1                       Apply to every row separately:
                  =&'O'#]                           Get the O's in the row.
       (#~=&' ')                                    Get the spaces in the row.
                ,                                   Join them, spaces come first.
  [:|:                                            Reverse axes again.

```

---

Examples (note that multiline strings start with `0 : 0` and end withh a bracket):

```
   f 0 : 0
O
OO O
OOOOO
) NB. output starts now
O
O
OO
OO
OOO
   f 0 : 0
O O
O O
) NB. Output starts now.

OO
OO

```

# Answer
> 2 votes
# Python 2 (69) (79)

```
for c in sorted(zip(*raw_input().split("\\n"))):print''.join(c[::-1])

```

Takes input padded with spaces so all lines have equal length. The `split` creates an arrat of each line. The `zip` effectively transposes the array. Then, the `sorted` sorts tuples in lexicographic order, causing all coins to fall to the bottom. Finally, we print each line, turning it back into a string, though we must reverse it first. Doing `print'O'*c.count('O')` is equivalent and uses the same number of characters.

Example run:

```
>> O    \nOO O \nOOOOO
O
O
OO
OO
OOO

```

# Answer
> 2 votes
### Haskell — 86

Just learning, so I'm sure this can be improved.

```
import Data.List
c=putStr.unlines.filter(/="").sort.map(filter(/=' ')).transpose.lines

```

Sample Input:

```
let a = "O    \nOO O \nOOOOO"
let b = " O O \n O O "
c a
c b

```

Sample Output:

```
O
O
OO
OO
OOO

OO
OO

```

# Answer
> 1 votes
## C, ~~167~~ 119 bytes

This shorter version is (unfortunately?) much clearer than the original too.

```
m;j;b[99];r;main(){while(j=getchar()+1)j-11?m+=j-33&&++b[r]>m:++r;for(j=r;m+1;putchar(j--?m<b[j]?79:32:(j=r,m--,10)));}

```

# Answer
> 0 votes
# Racket: 130

```
(let l((a'()))(let((b(sort(string->list(read-line))char<?)))(if
(null? b)(apply map(λ x(map display x)(newline))a)(l(cons b a)))))

```

It requires you pad with spaces so the lines are equal lemgth.

# Answer
> 0 votes
## C# - ~~209~~ 174 bytes

Right, I have to try this Code golf at some point I reckon. Created a function (r) that rotates the board and prints it. I guess I'm cheating a little when I am printing my char array, but if you cannot figure out why you shouldn't be mad :)

Thanks to ProgramFOX for the tips :)

```
void r(string s){int x=s.IndexOf('\n'),j,i=-1,k,z=x+1;var y=new char[x*x+x];for(;++i<x;y[z*(i+1)-1]='\n')for(k=j=x;j>0;)if(s[i*z+--j]=='0')y[k--*z-i-2]='0';Console.Write(y);}

```

Cheat

> `new char[x*x+x]` fills the array with `'\0'` and not `' '`

---
Tags: code-golf, simulation
---


title: Guess the word (aka Lingo)

text:
# Question
Title: Guess the word (aka Lingo)
The goal of this challenge is to write a program able to guess a word in the smallest possible number of attempts. It is based on the concept of the Lingo TV show (http://en.wikipedia.org/wiki/Lingo\_(U.S.\_game\_show)).

## Rules

Given a word length passed as the first argument on its command line, the player program disposes of **five** attempts to guess the word by writing a guess on its standard output followed by a single `\n` character.

After a guess is made, the program receives a string on its standard input, also followed by a single `\n` character.

The string has the same length as the word to guess and is comprised of a sequence of the following characters:

* `X`: which means that the given letter is not present in the word to guess
* `?`: which means that the given letter is present in the word to guess, but at another location
* `O`: which means that the letter at this location has been correctly guessed

For example, if the word to guess is `dents`, and the program sends the word `dozes`, it will receive `OXX?O` because `d` and `s` are correct, `e` is misplaced, and `o` and `z` are not present.

Be careful that if a letter is present more times in the guessing attempt than in the word to guess, it will **not** be marked as `?` and `O` more times than the number of occurences of the letter in the word to guess. For example, if the word to guess is `cozies` and the program sends `tosses`, it will receive `XOXXOO` because there is only one `s` to locate.

Words are chosen from an english word list. If the word sent by the program is not a valid word of the correct length, the attempt is considered as an automatic failure and only `X`'s are returned.
The player program should assume that a file named `wordlist.txt` and containing one word per line is present in the current working directory, and can be read as necessary.
Guesses should only be comprised of alphabetic low-case characters (`[a-z]`).
No other network or file operations are allowed for the program.

The game ends when a string only comprised of `O` is returned or after the program has made 5 attempts and was not able to guess the word.

## Scoring

The score of a game is given by the given formula:

```
score = 100 * (6 - number_of_attempts)

```

So if the word is correctly guessed on the first try, 500 points are given. The last try is worth 100 points.

Failure to guess the word grants zero points.

## The pit

Player programs will be evaluated by trying to have them guess **100** random words for each word length between 4 and 13 characters inclusively.
Random word selection will be done by advance so all entries will have to guess the same words.

The winning program, and accepted answer, will be the one to reach the highest score.

Programs will be run in an Ubuntu virtual machine, using the code at https://github.com/noirotm/lingo. Implementations in any language are accepted as long as reasonable instructions to compile and/or run them are provided.

I'm providing a few test implementations in ruby in the git repository, feel free to take inspiration from them.

This question will be periodically updated with rankings for published answers so challengers can improve their entries.

The official final evaluation will take place on the **1st of July**.

## Update

Entries can now assume the presence of `wordlistN.txt` files to speed up reading the word list for the current word length for N between 4 and 13 inclusively.

For example, there is a `wordlist4.txt` file containing all four letter words, and `wordlist10.txt` containing all ten letter words, and so on.

## First round results

At the date of 2014-07-01, three entries have been submitted, with the following results:

```
                        4       5       6       7       8       9       10      11      12      13      Total
./chinese-perl-goth.pl  8100    12400   15700   19100   22100   25800   27900   30600   31300   33600   226600
java Lingo              10600   14600   19500   22200   25500   28100   29000   31600   32700   33500   247300
./edc65                 10900   15800   22300   24300   27200   29600   31300   33900   33400   33900   262600

** Rankings **
1: ./edc65 (262600)
2: java Lingo (247300)
3: ./chinese-perl-goth.pl (226600)

```

All entries performed consistently, with a clear winner, being @edc65's C++'s entry.

All contestants are pretty awesome. I have been unable so far to even beat @chinese-perl-goth.
If more entries are submitted, another evaluation will take place. Current entries can also be improved if you feel like you can do better.

# Answer
# C++ 267700 Points

A porting from an old MasterMind engine.
Differences from MasterMind:

* More slots
* More symbols
* Bigger solution space (but non so much, because not all symbols combination allowed)
* The response is much informative, so we have more information after each guess
* The response is slower to generate and that's a pity because my algorithm have to do it a lot.

The basic idea is choosing the word that minimize the solution space. The algorithm is really slow for the first guess (I mean 'days'), but the best first guess depends only on the word len, so it's hardcoded in the source. The other guesses are done in matter of seconds.

**The Code**

(Compile with g++ -O3)

```
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <ctime>
#include <cstdlib>

using namespace std;

class LRTimer
{
private:
    time_t start;
public:
    void startTimer(void)
    {
        time(&start);
    }

    double stopTimer(void)
    {
        return difftime(time(NULL),start);
    }

};

#define MAX_WORD_LEN 15
#define BIT_QM 0x8000

LRTimer timer;
int size, valid, wordLen;

string firstGuess[] = { "", "a", "as", "iao", "ares",
    "raise", "sailer", "saltier", "costlier", "clarities",
    "anthelices", "petulancies", "incarcerates", "allergenicity" };

class Pattern
{
public:
    char letters[MAX_WORD_LEN];
    char flag;
    int mask;

    Pattern()
        : letters(), mask(), flag()
    {
    }

    Pattern(string word)
        : letters(), mask(), flag()
    {
        init(word);
    }

    void init(string word)
    {
        const char *wdata = word.data();
        for(int i = 0; i < wordLen; i++) {
            letters[i] = wdata[i];
            mask |= 1 << (wdata[i]-'a');
        }
    }

    string dump()
    {
        return string(letters);
    }

    int check(Pattern &secret)
    {
        if ((mask & secret.mask) == 0)
            return 0;

        char g[MAX_WORD_LEN], s[MAX_WORD_LEN];
        int r = 0, q = 0, i, j, k=99;
        for (i = 0; i < wordLen; i++)
        {
            g[i] = (letters[i] ^ secret.letters[i]);
            if (g[i])
            {
                r += r;
                k = 0;
                g[i] ^= s[i] = secret.letters[i];
            }
            else
            {
                r += r + 1;
                s[i] = 0;
            }
        }
        for (; k < wordLen; k++)
        {
            q += q;
            if (g[k])
            {
                for (j = 0; j < wordLen; j++)
                    if (g[k] == s[j])
                    {
                        q |= BIT_QM;
                        s[j] = 0;
                        break;
                    }
            }
        }
        return r|q;
    }

    int count(int ck, int limit);

    int propcheck(int limit);

    void filter(int ck);
};

string dumpScore(int ck)
{
    string result(wordLen, 'X');
    for (int i = wordLen; i--;)
    {
        result[i] = ck & 1 ? 'O' : ck & BIT_QM ? '?' : 'X';
        ck >>= 1;
    }
    return result;
}

int parseScore(string ck)
{
    int result = 0;
    for (int i = 0; i < wordLen; i++)
    {
        result += result + (
            ck[i] == 'O' ? 1 : ck[i] == '?' ? BIT_QM: 0
        );
    }
    return result;
}

Pattern space[100000];

void Pattern::filter(int ck)
{
    int limit = valid, i = limit;
//  cerr << "Filter IN Valid " << setbase(10) << valid << " This " << dump() << "\n";

    while (i--)
    {
        int cck = check(space[i]);
//      cerr << setbase(10) << setw(8) << i << ' ' << space[i].dump()
//          << setbase(16) << setw(8) << cck << " (" << Pattern::dumpScore(cck) << ") ";

        if ( ck != cck )
        {
//          cerr << " FAIL\r" ;
            --limit;
            if (i != limit)
            {
                Pattern t = space[i];
                space[i] = space[limit];
                space[limit] = t;
            }
        }
        else
        {
//          cerr << " PASS\n" ;
        }
    }
    valid = limit;
//  cerr << "\nFilter EX Valid " << setbase(10) << valid << "\n";
};

int Pattern::count(int ck, int limit)
{
    int i, num=0;
    for (i = 0; i < valid; ++i)
    {
        if (ck == check(space[i]))
            if (++num >= limit) return num;
    }
    return num;
}

int Pattern::propcheck(int limit)
{
    int k, mv, nv;

    for (k = mv = 0; k < valid; ++k)
    {
        int ck = check(space[k]);
        nv = count(ck, limit);
        if (nv >= limit)
        {
            return 99999;
        }
        if (nv > mv) mv = nv;
    }
    return mv;
}

int proposal(bool last)
{
    int i, minnv = 999999, mv, result;

    for (i = 0; i < valid; i++)
    {
        Pattern& guess = space[i];
//      cerr << '\r' << setw(6) << i << ' ' << guess.dump();
        if ((mv = guess.propcheck(minnv)) < minnv)
        {
//          cerr << setw(6) << mv << ' ' << setw(7) << setiosflags(ios::fixed) << setprecision(0) << timer.stopTimer() << " s\n";
            minnv = mv;
            result = i;
        }
    }
    if (last)
        return result;
    minnv *= 0.75;
    for (; i<size; i++)
    {
        Pattern& guess = space[i];
//      cerr << '\r' << setw(6) << i << ' ' << guess.dump();
        if ((mv = guess.propcheck(minnv)) < minnv)
        {
//          cerr << setw(6) << mv << ' ' << setw(7) << setiosflags(ios::fixed) << setprecision(0) << timer.stopTimer() << " s\n";
            minnv = mv;
            result = i;
        }
    }
    return result;
}

void setup(string wordfile)
{
    int i = 0;
    string word;
    ifstream infile(wordfile.data());
    while(infile >> word)
    {
        if (word.length() == wordLen) {
            space[i++].init(word);
        }
    }
    infile.close();
    size = valid = i;
}

int main(int argc, char* argv[])
{
    if (argc < 2)
    {
        cerr << "Specify word length";
        return 1;
    }

    wordLen = atoi(argv[1]);

    timer.startTimer();
    setup("wordlist.txt");
    //cerr << "Words " << size
    //  << setiosflags(ios::fixed) << setprecision(2)
    //  << " " << timer.stopTimer() << " s\n";

    valid = size;
    Pattern Guess = firstGuess[wordLen];
    for (int t = 0; t < 5; t++)
    {
        cout << Guess.dump() << '\n' << flush;
        string score;
        cin >> score;
        int ck = parseScore(score);
        //cerr << "\nV" << setw(8) << valid << " #"
        //  << setw(3) << t << " : " << Guess.dump()
        //  << " : " << score << "\n";
        if (ck == ~(-1 << wordLen))
        {
            break;
        }
        Guess.filter(ck);
        Guess = space[proposal(t == 3)];
    }
    // cerr << "\n";

    double time = timer.stopTimer();
    //cerr << setiosflags(ios::fixed) << setprecision(2)
    //   << timer.stopTimer() << " s\n";

    return 0;
}

```

**My scores**

Evaluation with lingo, 100 rounds:

```
4   9000
5   17700
6   22000
7   25900
8   28600
9   29700
10  31000
11  32800
12  33500
13  34900

```

Total 265'100

**Self evalueted scores**

Here are my average points, scored on the whole wordlist. Not completely relyable because some detail of algorithm has changed during the tests.

```
 4 # words  6728 PT AVG   100.98 87170.41 s
 5 # words 14847 PT AVG   164.44 42295.38 s
 6 # words 28127 PT AVG   212.27 46550.00 s
 7 # words 39694 PT AVG   246.16 61505.54 s
 8 # words 49004 PT AVG   273.23 63567.45 s
 9 # words 50655 PT AVG   289.00 45438.70 s
10 # words 43420 PT AVG   302.13 2952.23 s
11 # words 35612 PT AVG   323.62 3835.00 s
12 # words 27669 PT AVG   330.19 5882.98 s
13 # words 19971 PT AVG   339.60 2712.98 s

```

According to these numbers, my average score should be near 257'800

**PIT SCORE**

At last I installed Ruby, so now I have an 'official' score:

```
    4       5       6       7       8       9      10      11      12      13   TOTAL
10700   16300   22000   25700   27400   30300   32000   33800   34700   34800   267700

```
> 5 votes

# Answer
## Java, 249700 points (beats Chinese Perl Goth in my test)

Updated ranklist:

```
                        4       5       6       7       8       9       10      11      12      13      Total
perl chinese_perl_goth.pl 6700  12300   16900   19200   23000   26100   28500   29600   32100   33900   228300
java Lingo              9400    14700   18900   21000   26300   28700   30300   32400   33800   34200   249700

```

Here is the **old** ranklist using `pit.rb`:

```
                        4       5       6       7       8       9       10      11      12      13      Total
ruby player-example.rb  200     400     400     500     1800    1400    1700    1600    3200    4400    15600
ruby player-example2.rb 2700    3200    2500    4300    7300    6300    8200    10400   13300   15000   73200
ruby player-example3.rb 4500    7400    9900    13700   15400   19000   19600   22300   24600   27300   163700
perl chinese_perl_goth.pl 6400  14600   16500   21000   22500   26000   27200   30600   32500   33800   231100
java Lingo              4800    13100   16500   21400   27200   29200   30600   32400   33700   36100   245000

** Rankings **
1: java Lingo (245000)
2: perl chinese_perl_goth.pl (231100)
3: ruby player-example3.rb (163700)
4: ruby player-example2.rb (73200)
5: ruby player-example.rb (15600)

```

~~Compared to @chineseperlgoth, I lose in shorter words (\< 6 chars) but I win in longer words (\>= 6 chars).~~

The idea is similar to @chineseperlgoth, it's just that my main idea is about finding the guess (can be any word of the same length, not necessarily one of the remaining possibilities) which gives the most information for the next guess.

~~Currently I'm still playing with the formula, but for the scoreboard above, I choose the word which will yield the minimum for:~~

~~```
-num_confusion * entropy

```~~

The latest version uses different scoring to find next best guess, which is maximizing the number of "single possibility" after the current guess. This is done by trying all words in pruned wordlist (to save time) on all possible candidates, and see which guess is more probable to produce "single possibility" (that is, after this guess there will only be one possible answer) for the next guess.

So for example this run:

```
Starting new round, word is boons
Got:   seora
Sent:  ?XOXX
Got:   topsl
Sent:  XOX?X
Got:   monks
Sent:  XO?XO
Got:   bewig
Sent:  OXXXX
Got:   boons
Sent:  OOOOO
Round won with score 100

```

From the first three guesses, we already got "\*oo\*s" with an "n" somewhere and we still need to figure out one more letter. Now the beauty of this algorithm is that instead of guessing words which are similar to that form, it instead guesses the word which has no relation to previous guesses at all, trying to give more letters, hopefully revealing the missing letter. In this case it happens to also get the position for the missing "b" correctly, and concludes with the correct final guess "boons".

Here is the code:

```
import java.util.*;
import java.io.*;

class Lingo{
    public static String[] guessBestList = new String[]{
                                "",
                                "a",
                                "sa",
                                "tea",
                                "orae",
                                "seora", // 5
                                "ariose",
                                "erasion",
                                "serotina",
                                "tensorial",
                                "psalterion", // 10
                                "ulcerations",
                                "culteranismo",
                                "persecutional"};
    public static HashMap<Integer, ArrayList<String>> wordlist = new HashMap<Integer, ArrayList<String>>();

    public static void main(String[] args){
        readWordlist("wordlist.txt");
        Scanner scanner = new Scanner(System.in);
        int wordlen = Integer.parseInt(args[0]);
        int roundNum = 5;
        ArrayList<String> candidates = new ArrayList<String>();
        candidates.addAll(wordlist.get(wordlen));
        String guess = "";
        while(roundNum-- > 0){
            guess = guessBest(candidates, roundNum==4, roundNum==0);
            System.out.println(guess);
            String response = scanner.nextLine();
            if(isAllO(response)){
                break;
            }
            updateCandidates(candidates, guess, response);
            //print(candidates);
        }
    }

    public static void print(ArrayList<String> candidates){
        for(String str: candidates){
            System.err.println(str);
        }
        System.err.println();
    }

    public static void readWordlist(String path){
        try{
            BufferedReader reader = new BufferedReader(new FileReader(path));
            while(reader.ready()){
                String word = reader.readLine();
                if(!wordlist.containsKey(word.length())){
                    wordlist.put(word.length(), new ArrayList<String>());
                }
                wordlist.get(word.length()).add(word);
            }
        } catch (Exception e){
            System.exit(1);
        }
    }

    public static boolean isAllO(String response){
        for(int i=0; i<response.length(); i++){
            if(response.charAt(i) != 'O') return false;
        }
        return true;
    }

    public static String getResponse(String word, String guess){
        char[] wordChar = word.toCharArray();
        char[] result = new char[word.length()];
        Arrays.fill(result, 'X');
        for(int i=0; i<guess.length(); i++){
            if(guess.charAt(i) == wordChar[i]){
                result[i] = 'O';
                wordChar[i] = '_';
            }
        }
        for(int i=0; i<guess.length(); i++){
            if(result[i] == 'O') continue;
            for(int j=0; j<wordChar.length; j++){
                if(result[j] == 'O') continue;
                if(wordChar[j] == guess.charAt(i)){
                    result[i] = '?';
                    wordChar[j] = '_';
                    break;
                }
            }
        }
        return String.valueOf(result);
    }

    public static void updateCandidates(ArrayList<String> candidates, String guess, String response){
        for(int i=candidates.size()-1; i>=0; i--){
            String candidate = candidates.get(i);
            if(!response.equals(getResponse(candidate, guess))){
                candidates.remove(i);
            }
        }
    }

    public static int countMatchingCandidates(ArrayList<String> candidates, String guess, String response){
        int result = 0;
        for(String candidate: candidates){
            if(response.equals(getResponse(candidate, guess))){
                result++;
            }
        }
        return result;
    }

    public static String[] getSample(ArrayList<String> words, int size){
        String[] result = new String[size];
        int[] indices = new int[words.size()];
        for(int i=0; i<words.size(); i++){
            indices[i] = i;
        }
        Random rand = new Random(System.currentTimeMillis());
        for(int i=0; i<size; i++){
            int take = rand.nextInt(indices.length-i);
            result[i] = words.get(indices[take]);
            indices[take] = indices[indices.length-i-1];
        }
        return result;
    }

    public static String guessBest(ArrayList<String> candidates, boolean firstGuess, boolean lastGuess){
        if(candidates.size() == 1){
            return candidates.get(0);
        }
        String minGuess = candidates.get(0);
        int wordlen = minGuess.length();
        if(firstGuess && guessBestList[wordlen].length()==wordlen){
            return guessBestList[wordlen];
        }
        int minMatches = Integer.MAX_VALUE;
        String[] words;
        if(lastGuess){
            words = candidates.toArray(new String[0]);
        } else if (candidates.size()>10){
            words = bestWords(wordlist.get(wordlen), candidates, 25);
        } else {
            words = wordlist.get(wordlen).toArray(new String[0]);
        }
        for(String guess: words){
            double sumMatches = 0;
            for(String word: candidates){
                int matches = countMatchingCandidates(candidates, guess, getResponse(word, guess));
                if(matches == 0) matches = candidates.size();
                sumMatches += (matches-1)*(matches-1);
            }
            if(sumMatches < minMatches){
                minGuess = guess;
                minMatches = sumMatches;
            }
        }
        return minGuess;
    }

    public static String[] bestWords(ArrayList<String> words, ArrayList<String> candidates, int size){
        int[] charCount = new int[123];
        for(String candidate: candidates){
            for(int i=0; i<candidate.length(); i++){
                charCount[(int)candidate.charAt(i)]++;
            }
        }
        String[] tmp = (String[])words.toArray(new String[0]);
        Arrays.sort(tmp, new WordComparator(charCount));
        String[] result = new String[size+Math.min(size, candidates.size())];
        String[] sampled = getSample(candidates, Math.min(size, candidates.size()));
        for(int i=0; i<size; i++){
            result[i] = tmp[tmp.length-i-1];
            if(i < sampled.length){
                result[size+i] = sampled[i];
            }
        }
        return result;
    }

    static class WordComparator implements Comparator<String>{
        int[] charCount = null;

        public WordComparator(int[] charCount){
            this.charCount = charCount;
        }

        public Integer count(String word){
            int result = 0;
            int[] multiplier = new int[charCount.length];
            Arrays.fill(multiplier, 1);
            for(char chr: word.toCharArray()){
                result += multiplier[(int)chr]*this.charCount[(int)chr];
                multiplier[(int)chr] = 0;
            }
            return Integer.valueOf(result);
        }

        public int compare(String s1, String s2){
            return count(s1).compareTo(count(s2));
        }
    }
}

```
> 5 votes

# Answer
# Perl

There's still some room for improvement but at least it beats the included example players :)

Assumes write access to current directory for caching wordlists (to make it run a bit faster); will create `wordlist.lenN.stor` files using `Storable`. If this is an issue, remove `read_cached_wordlist` and change the code to use just `read_wordlist`.

## Explanation

First, I build a histogram of letter frequencies in all the words in the current wordlist (`build_histogram`). Then I need to choose my next guess - which is done by `find_best_word`. The scoring algorithm is just adding the histogram values together, skipping letters already seen. This gives me a word containing the most frequent letters in the wordlist. If there is more than one word with a given score, I choose one randomly. Having found a word, I send it to the game engine, read the reply then try and do something useful with it :)

I maintain a set of conditions, that is, letters that can occur at a given position in a word. On start, this is just simple `(['a'..'z'] x $len)`, but it is updated basing on the hints given in reply (see `update_conds`). I build a regex out of those conditions then and filter the wordlist through it.

During tests I have found out then that the aforementioned filtering doesn't handle `?`s too well, hence the second filter (`filter_wordlist_by_reply`). This takes advantage of the fact that a letter marked as `?` occurs in the word on a different position, and filters the wordlist accordingly.

These steps are repeated for every iteration of the main loop, unless the solution is found (or it is not possible to read from stdin anymore, which means a failure).

## Code

```
#!perl
use strict;
use warnings;
use v5.10;
use Storable;

$|=1;

sub read_wordlist ($) {
    my ($len) = @_;
    open my $w, '<', 'wordlist.txt' or die $!;
    my @wordlist = grep { chomp; length $_ == $len } <$w>;
    close $w;
    \@wordlist
}

sub read_cached_wordlist ($) {
    my ($len) = @_;
    my $stor = "./wordlist.len$len.stor";
    if (-e $stor) {
        retrieve $stor
    } else {
        my $wl = read_wordlist $len;
        store $wl, $stor;
        $wl
    }
}

sub build_histogram ($) {
    my ($wl) = @_;
    my %histo = ();
    for my $word (@$wl) {
        $histo{$_}++ for ($word =~ /./g);
    }
    \%histo
}

sub score_word ($$) {
    my ($word, $histo) = @_;
    my $score = 0;
    my %seen = ();
    for my $l ($word =~ /./g) {
        if (not exists $seen{$l}) {
            $score += $histo->{$l};
            $seen{$l} = 1;
        }
    }
    $score
}

sub find_best_word ($$) {
    my ($wl, $histo) = @_;
    my @found = (sort { $b->[0] <=> $a->[0] }
                 map [ score_word($_, $histo), $_ ], @$wl);
    return undef unless @found;
    my $maxscore = $found[0]->[0];
    my @max;
    for (@found) {
        last if $_->[0] < $maxscore;
        push @max, $_->[1];
    }
    $max[rand @max]
}

sub build_conds ($) {
    my ($len) = @_;
    my @c;
    push @c, ['a'..'z'] for 1..$len;
    \@c
}

sub get_regex ($) {
    my ($cond) = @_;
    local $" = '';
    my $r = join "", map { "[@$_]" } @$cond;
    qr/^$r$/
}

sub remove_cond ($$$) {
    my ($conds, $pos, $ch) = @_;
    return if (scalar @{$conds->[$pos]} == 1);
    return unless grep { $_ eq $ch } @{$conds->[$pos]};
    $conds->[$pos] = [ grep { $_ ne $ch } @{$conds->[$pos]} ]
}

sub add_cond ($$$) {
    my ($conds, $pos, $ch) = @_;
    return if (scalar @{$conds->[$pos]} == 1);
    return if grep { $_ eq $ch } @{$conds->[$pos]};
    push @{$conds->[$pos]}, $ch
}

sub update_conds ($$$$) {
    my ($word, $reply, $conds, $len) = @_;
    my %Xes;
    %Xes = ();
    for my $pos (reverse 0..$len-1) {
        my $r = substr $reply, $pos, 1;
        my $ch = substr $word, $pos, 1;

        if ($r eq 'O') {
            $conds->[$pos] = [$ch]
        }

        elsif ($r eq '?') {
            for my $a (0..$len-1) {
                if ($a == $pos) {
                    remove_cond $conds, $a, $ch
                } else {
                    unless (exists $Xes{$a} and $Xes{$a} eq $ch) {
                        add_cond($conds, $a, $ch);
                    }
                }
            }
        }

        elsif ($r eq 'X') {
            $Xes{$pos} = $ch;
            for my $a (0..$len-1) {
                remove_cond $conds, $a, $ch
            }
        }
    }
}

sub uniq ($) {
    my ($data) = @_;
    my %seen;
    [ grep { !$seen{$_}++ } @$data ]
}

sub filter_wordlist_by_reply ($$$) {
    my ($wl, $word, $reply) = @_;
    return $wl unless $reply =~ /\?/;
    my $newwl = [];
    my $len = length $reply;
    for my $pos (0..$len-1) {
        my $r = substr $reply, $pos, 1;
        my $ch = substr $word, $pos, 1;
        next unless $r eq '?';
        for my $a (0..$len-1) {
            if ($a != $pos) {
                if ('O' ne substr $reply, $a, 1) {
                    push @$newwl, grep { $ch eq substr $_, $a, 1 } @$wl
                }
            }
        }
    }
    uniq $newwl
}

my $len = $ARGV[0] or die "no length";
my $wl = read_cached_wordlist $len;
my $conds = build_conds $len;

my $c=0;
do {
    my $histo = build_histogram $wl;
    my $word = find_best_word $wl, $histo;
    die "no candidates" unless defined $word;
    say $word;
    my $reply = <STDIN>;
    chomp $reply;
    exit 1 unless length $reply;
    exit 0 if $reply =~ /^O+$/;
    update_conds $word, $reply, $conds, $len;
    $wl = filter_wordlist_by_reply $wl, $word, $reply;
    $wl = [ grep { $_ =~ get_regex $conds } @$wl ]
} while 1

```
> 3 votes

---
Tags: code-challenge, game, word
---


# Question
Title: Longest mathematical expression in a grid
Given a grid which contains these signs: 0..9, x, =, write the fastest code that outputs the longest string of connected (horizontally, vertically, and diagonally adjacent), distinct cells which is a mathematically valid expression formed on this grammar:

```
E := T '=' T
T := F 'x' T | F
F -> {0..9}+

```

More formally, a solution will have this form: an equality between a product of terms:

S = F0 x .. x Fp = Fp+1 x .. x Fn

I define N(S) = Max\_i(F\_i)

If two strings of the same length need to be compared, then I will compare their largest multiplicand. i.e. 30x3=90 \< 33x3=99 because 90 \< 99

## The grids

Grid 0: 3 x 3

```
13x
=73
481

```

which contains: `13x37=481`

Grid 1: 7 x 9

```
6996640
1127=39
186=940
8329706
3683980
6349307
75x19x0
5065350
0051900

```

which contains:

```
a=611333
b=599999
c=494687
d=531337
and a*b=366799188667
and c*d=262845506519

```

Grid 2: 8 x 8

```
1851x412
40081737
72330964
14461858
17604=67
89653745
13612200
14433193

```

Grid 3: 16 x 16

```
0951x71=7=41659x
958525855332=25x
8462=1x119191x76
993928209055089x
1523060251420490
=883152021094970
0146645532106152
87x96=294=x80675
7960948222x0440x
x577x987x0993241
29564563x=x5=800
03508x17050=6565

```

OK so after a short discussion in the comment sections, I am adding a few restrictions to allow me to do a fair comparison of solutions:

I will run the solution on my Macbook Pro which is 2,4 GHz Core 2 Duo running Mavericks. The language you are going to propose needs to be running natively on my computer, but fortunately, a lot of languages are available on OS X.

I will measure the quality of a program by comparing the time taken to find my hidden solution. Your program will probably find strings that are even longer that the one I hid in the first place, but this can not be avoided as I would need a program that enumerates all the solution of the grids I'm going to submit.. and this is the reason of this code golf..

# Answer
> 2 votes
# C, checks about 7,500,000 paths per second

So here is my first pass over this. It's quite horrible code because it's all in one huge `main` and the two (nested) loops over the left-hand side and right-hand-side of the equation are pretty much exactly the same, but well, it works.

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

#define MAX_SIZE 32

typedef struct {
    char symbol;
    int visited;
} cell;

typedef struct {
    int x;
    int y;
} coord;

static cell grid[MAX_SIZE][MAX_SIZE];
static int nEquals = 0;
static coord equals[MAX_SIZE*MAX_SIZE];

static coord dirs[8] = {
    { .x = -1, .y = -1 },
    { .x =  0, .y = -1 },
    { .x =  1, .y = -1 },
    { .x =  1, .y =  0 },
    { .x =  1, .y =  1 },
    { .x =  0, .y =  1 },
    { .x = -1, .y =  1 },
    { .x = -1, .y =  0 },
};

static char best_string[2*MAX_SIZE*MAX_SIZE+1];
static int best_length = 0;
static unsigned long long best_factor;

int main(int argc, char *argv[])
{
    FILE *fp = fopen("grid.txt", "r");
    if (!fp) perror("Memory allocation failed"), exit(1);

    fseek(fp, 0L, SEEK_END);
    long lSize = ftell(fp);
    rewind(fp);

    char *buffer = calloc(1, lSize+1);
    if (!buffer)
    {
        fclose(fp);
        perror("Memory allocation failed");
        exit(1);
    }

    if (1 != fread(buffer, lSize, 1, fp))
    {
        fclose(fp);
        free(buffer);
        perror("Reading file failed");
        exit(1);
    }

    fclose(fp);

    char *cp;
    cp = buffer;
    int width = (int)strtol(cp, &cp, 10);
    int height = (int)strtol(cp, &cp, 10);

    ++cp;
    int i, j;
    for (j = 0; j < height; ++j)
    {
        for (i = 0; i < width; ++i)
        {
            grid[j][i].symbol = *cp;
            grid[j][i].visited = 0;

            if (*cp == '=')
            {
                equals[nEquals].x = i;
                equals[nEquals].y = j;
                ++nEquals;
            }
            ++cp;
        }
        ++cp;
    }

    printf("Analysing %d x %d grid...\n", width, height);

    unsigned long long strings_checked = 0;

    clock_t start = clock();

    for (j = 0; j < nEquals; ++j)
    {
        char expression[2*MAX_SIZE*MAX_SIZE+1];
        coord lpos = equals[j];
        coord rpos = equals[j];

        // Set to spaces to ease parsing
        for (i = 0; i < 2*MAX_SIZE*MAX_SIZE+1; ++i)
            expression[i] = ' ';

        int center = MAX_SIZE*MAX_SIZE;
        expression[center] = '=';

        int lhs_size = 0;
        int lhs_n_factors = 0;

        int lhs_dirs[MAX_SIZE*MAX_SIZE];
        for (i = 0; i < MAX_SIZE*MAX_SIZE; ++i)
            lhs_dirs[i] = -2;
        int rhs_dirs[MAX_SIZE*MAX_SIZE];
        for (i = 0; i < MAX_SIZE*MAX_SIZE; ++i)
            rhs_dirs[i] = -2;

        unsigned long long lhs_factors[MAX_SIZE*MAX_SIZE];
        unsigned long long lhs_max_factors[MAX_SIZE*MAX_SIZE];
        unsigned long long lhs_products[MAX_SIZE*MAX_SIZE];
        lhs_max_factors[0] = 0;
        lhs_products[0] = 1;

        while (lhs_size >= 0)
        {
            int dir = ++lhs_dirs[lhs_size];
            char lmost_char = expression[center-lhs_size];

            if (dir == -1)
            {
                grid[lpos.y][lpos.x].visited = 1;

                if (lmost_char == 'x')
                {
                    unsigned long long factor = strtoll(expression+center-lhs_size + 1, NULL, 10);
                    lhs_factors[lhs_n_factors] = factor;
                    ++lhs_n_factors;
                    if (factor > lhs_max_factors[lhs_n_factors-1])
                        lhs_max_factors[lhs_n_factors] = factor;
                    else
                        lhs_max_factors[lhs_n_factors] = lhs_max_factors[lhs_n_factors-1];
                    lhs_products[lhs_n_factors] = lhs_products[lhs_n_factors-1] * factor;
                    continue;
                }
                else if (lmost_char == '=')
                    continue;
                else
                {
                    unsigned long long factor = strtoll(expression+center-lhs_size, NULL, 10);
                    unsigned long long max_lhs_factor;
                    if (factor > lhs_max_factors[lhs_n_factors])
                        max_lhs_factor = factor;
                    else
                        max_lhs_factor = lhs_max_factors[lhs_n_factors];

                    unsigned long long lhs_product = lhs_products[lhs_n_factors] * factor;

                    int rhs_size = 0;

                    int rhs_n_factors = 0;
                    unsigned long long max_rhs_factor = 0;

                    unsigned long long rhs_factors[MAX_SIZE*MAX_SIZE];
                    unsigned long long max_factors[MAX_SIZE*MAX_SIZE];
                    unsigned long long rhs_products[MAX_SIZE*MAX_SIZE];
                    max_factors[0] = max_lhs_factor;
                    rhs_products[0] = 1;

                    char *rhs_factor_pointers[MAX_SIZE*MAX_SIZE];
                    rhs_factor_pointers[0] = expression+center+1;

                    while (rhs_size >= 0)
                    {
                        int dir = ++rhs_dirs[rhs_size];
                        char rmost_char = expression[center+rhs_size];

                        if (dir == -1)
                        {
                            grid[rpos.y][rpos.x].visited = 1;

                            if (rmost_char == 'x')
                            {
                                factor = strtoll(rhs_factor_pointers[rhs_n_factors], NULL, 10);
                                rhs_factors[rhs_n_factors] = factor;
                                ++rhs_n_factors;
                                rhs_factor_pointers[rhs_n_factors] = expression + center + rhs_size + 1;
                                if (factor > max_factors[rhs_n_factors-1])
                                    max_factors[rhs_n_factors] = factor;
                                else
                                    max_factors[rhs_n_factors] = max_factors[rhs_n_factors-1];
                                rhs_products[rhs_n_factors] = rhs_products[rhs_n_factors-1] * factor;
                                continue;
                            }
                            else if (rmost_char == '=')
                                continue;
                            else
                            {
                                // check for solution
                                ++strings_checked;

                                factor = strtoll(rhs_factor_pointers[rhs_n_factors], NULL, 10);
                                unsigned long long max_factor;
                                if (factor > max_factors[rhs_n_factors])
                                    max_factor = factor;
                                else
                                    max_factor = max_factors[rhs_n_factors];

                                unsigned long long rhs_product = rhs_products[rhs_n_factors] * factor;

                                //printf("%.19s = %d\n", expression + center - 9, rhs_product);
                                //  printf("%.51s\n", expression + center - 25);
                                int length = rhs_size + lhs_size + 1;

                                if (lhs_product == rhs_product &&
                                    (length > best_length ||
                                     length == best_length && max_factor > best_factor))
                                {
                                    best_length = length;
                                    best_factor = max_factor;
                                    memcpy(best_string, expression + center - lhs_size, length);
                                    best_string[length] = 0;
                                }

                            }
                        }
                        else if (dir < 8)
                        {
                            coord step = dirs[dir];
                            int new_x = rpos.x + step.x;
                            int new_y = rpos.y + step.y;
                            char new_char;

                            if (new_x < 0 || new_x >= width ||
                                new_y < 0 || new_y >= height ||
                                grid[new_y][new_x].visited ||
                                (new_char = grid[new_y][new_x].symbol) == '=' ||
                                new_char == 'x' && (rmost_char == 'x' || rmost_char == '=')) continue;

                            // TODO: Should diagonally crossing paths be disallowed, too?

                            ++rhs_size;

                            rpos.x = new_x;
                            rpos.y = new_y;
                            expression[center+rhs_size] = new_char;
                        }
                        else
                        {
                            if (rmost_char == 'x')
                                --rhs_n_factors;

                            rhs_dirs[rhs_size] = -2;
                            if (rmost_char != '=') expression[center+rhs_size] = ' ';
                            grid[rpos.y][rpos.x].visited = 0;

                            --rhs_size;
                            coord step = dirs[rhs_dirs[rhs_size]];
                            rpos.x -= step.x;
                            rpos.y -= step.y;
                        }
                    }
                }
            }
            else if (dir < 8)
            {
                coord step = dirs[dir];
                int new_x = lpos.x + step.x;
                int new_y = lpos.y + step.y;
                char new_char;

                if (new_x < 0 || new_x >= width ||
                    new_y < 0 || new_y >= height ||
                    grid[new_y][new_x].visited ||
                    (new_char = grid[new_y][new_x].symbol) == '=' ||
                    new_char == 'x' && (lmost_char == 'x' || lmost_char == '=')) continue;

                // TODO: Should diagonally crossing paths be disallowed, too?

                ++lhs_size;

                lpos.x = new_x;
                lpos.y = new_y;
                expression[center-lhs_size] = new_char;
            }
            else
            {
                if (lmost_char == 'x')
                    --lhs_n_factors;

                lhs_dirs[lhs_size] = -2;
                expression[center-lhs_size] = ' ';
                grid[lpos.y][lpos.x].visited = 0;

                --lhs_size;
                coord step = dirs[lhs_dirs[lhs_size]];
                lpos.x -= step.x;
                lpos.y -= step.y;
            }
        }
    }

    clock_t end = clock();
    float seconds = (float)(end - start) / CLOCKS_PER_SEC;

    printf("Checked %llu paths.\n", strings_checked);

    printf("Took %f seconds.\n", seconds);

    printf("Result: %s\n", best_string);
}

```

This expects the input stored in a file `grid.txt`. The first line is the space-separated size of the grid, which is followed by the grid itself. Like:

```
3 3
13x
=73
481

```

The algorithm is currently checking all possible well-formed paths (brute force). By well-formed, I mean that paths containing `xx` or two `=` are skipped, and I only start looking for paths starting from a `=` in both directions. Basically, I check all possible LHSs and for each such path, I check all possible RHSs. Over the next few days, I plan to add several optimisations to skip more paths, since the runtime per path will only go up and not down from here.

This will run into some problems with grid sizes of more than some 20 cells, due to integer overflow. I'll have to use some bigint-library when I get to solving those in a reasonable amount of time (which, I'm afraid, will reduce the paths/second a bit).

Currently, the largest sizes that can be solved in a reasonable amount of time at the moment are 7x3 or 5x4 (both taking under two minutes). 8x3 would take about half an hour, and 9x3 or 6x4 or 5x5 would take a few hours (between 1 and 7 I think).

**EDIT:** Managed to speed it up by close to 20 percent, because now I'm parsing each multiplicand when it's "locked" (i.e. when an `x` next to it has been parsed) instead of parsing the entire right-hand side for each possible path. And I should add that I observed those 20% for a grid where there's only a single `x` to be found, so I expect the performance gain for grids with many `x` to actually be quite substantial. Next stop: bigints.

# Answer
> 1 votes
### Python + networkx (Bruteforce, checks about 10000 paths per second on my machine)

It's not fast, but it works at least. Checks literally every path.

Amount of cycles necessary can be found here. This program solved a 5\*6 in half an hour.

TODO: ~~replace `eval` by something less terrible.~~  Done.

```
__author__ = 'Synthetica'

import networkx as nx
import itertools as it
import time as tm

def main():
    longest = 0
    data = ['6996640', '1127=39', '186=940', '8329706', '3683980', '6349307',
            '75x19x0', '5065350', '0051900']

    hor = len(data[0])
    vert = len(data)

    threads = 8
    G = nx.grid_2d_graph(vert, hor)
    # Q = qu.LifoQueue(maxsize=1000)
    #W = mp.Pool(threads)
    #W.map_async(evalexpr, [Q]*threads)
    printevery = 10**4
    tested = 0
    t = tm.time()
    for node in it.product(G.nodes(), repeat=2):
        if node[0]==node[1]:
            continue
        for path in nx.all_simple_paths(G, source=node[0], target=node[1]):
            tested += 1
            path = "".join(data[x][y] for x, y in path)
            if tested > printevery:
                ot = t
                t = tm.time()
                tested = 0
                print printevery, "tested. Speed:", printevery/(t-ot), "s**-1"
            if not all((path.count('=')==1, 'x' in path, len(path) >= longest)):
                continue
            #newpath = path.replace('=', '==').replace('x', '*')
            try:
                #print "Calling eval on", newpath
                parts = path.split("=")
                part0 = parts[0].split('x')
                part1 = parts[1].split('x')

                part0 = map(int,part0)
                part1 = map(int,part1)

                part0 = reduce(int.__mul__, part0)
                part1 = reduce(int.__mul__, part1)

                result = part0 == part1

            except:
                result = False
            if result:
                print 'Found new best:',path
                longest = len(path)

if __name__ == "__main__":
    main()

```

---
Tags: math, fastest-code, expression-building
---


# Question
Title: Convert binary search tree into ordered linked list
Write the shortest possible program that turns a binary search tree into an ordered doubly-linked list, by modifying the pointers to the left and the right children of each node.

**Arguments**: a pointer to the root of the binary tree.

**Return value**: a pointer to the head of the linked list.

The binary tree node has three fields:

* the ordering key, an integer
* a pointer to the left child
* a pointer to the right child

The pointers should be modified so that "left child" points to the previous node of the list and "right child" points to the next node of the list.

* Y̶o̶u̶'̶r̶e̶ ̶n̶o̶t̶ ̶a̶l̶l̶o̶w̶e̶d̶ ̶t̶o̶ ̶c̶r̶e̶a̶t̶e̶/̶a̶l̶l̶o̶c̶a̶t̶e̶ ̶m̶o̶r̶e̶ ̶n̶o̶d̶e̶s̶.
* The tree and the list are both ordered increasingly.
* You have to write the implementation of the node object.
* The tree is not necessarily complete

Example:

```
input:
   5 <- root
  / \
 2   8
/ \ / \
1 4 6 9

output:
head -> 1-2-4-5-6-8-9
```

EDIT: I removed the 1st rule, since people complained it was not possible to do using functional programming languages.

# Answer
> 2 votes
# Python: 100

```
class N:l=r=v=None
def T(p,q=None):
 if not p:return q
 r=p.r=T(p.r,q)
 if r:r.l=p
 return T(p.l,p)

```

## Ungolfed Version

```
class Node:
    left = right = value = None

def transform(node, next=None):
    """
    node: head node to convert
    next: next node for the tail node to connect
    return: The converted head
    """
    if not node:
        return next
    node.right = transform(node.right, next)
    if node.right:
        node.right.left = node
    return transform(node.left, node)

```

Instead of returning a (head, tail) pair, in my solution, a `next` node is passed as argument to the transform function so that it only need to return the head node. This make the code shorter and cleaner.

# Answer
> 1 votes
# Javascript 238 (163 not including the input tree declaration/initialization)

Tested in google chrome. To see the result, open the javascript console and traverse any node of the list.

jsfiddle: http://jsfiddle.net/49grd/1/

```
b={val:5,n1:{val:2,n1:{val:1},n2:{val:4}},n2:{val:8,n1:{val:6},n2:{val:9}}}
o=[]
function r(t){if(t.n1)r(t.n1);o.push(t);if(t.n2)r(t.n2);}
r(b);
for(var i=0;i<o.length;i++){if(o[i-1])o[i].n1=o[i-1];if(o[i+1])o[i].n2=o[i+1];}
console.dir(o[0]);

```

**Ungolfed:**

jsfiddle avbailable here: http://jsfiddle.net/s8PsU/

```
var binaryTree =
{
    val: 5,
    n1: {
        val: 2,
        n1: { val: 1},
        n2: { val: 4}
    },
    n2: {
        val: 8,
        n1: {val: 6},
        n2: {val: 9}
    }
}

var orderedNodes = []

function traverse(t)
{
if(t.n1)
    traverse(t.n1);
orderedNodes.push(t);
if(t.n2)
    traverse(t.n2);
}
traverse(binaryTree);

for(var i = 0; i < orderedNodes.length; i++)
{
if(orderedNodes[i-1])
    orderedNodes[i].n1 = orderedNodes[i-1];
if(orderedNodes[i+1])
    orderedNodes[i].n2 = orderedNodes[i+1];
}

console.dir(orderedNodes[0]);

```

# Answer
> 1 votes
# Scala - (207/188) Characters

```
class n(a:n,b:Int,c:n){var l:n=a;var n:Int=b;var r:n=c}def t(r:n):(n,n)=(if(r.l==null)r
else{val y=t(r.l);r.l=y._2;y._2.r=r;y._1},if(r.r==null)r
else{val y=t(r.r);r.r=y._1;y._1.l=r;y._2})
def a(r:n)=t(r)._1

```

Without the function a wich just gets the head of the list, this are 188 characters.

Idea is: return a tuple wich consist of the most left element of you and your children and the most right element. Also link your left element to the most element of your left children and your right element to the most left element of your right children.

Code for printing the list:

```
def printN(r:n)=if(r==null)"null" else (r.n + "->" +printN(r.r))

```

Ungolfed:

```
class Node(a:n,b:Int,c:n){//our Node Class
   var l:Node=a //left child
   var n:Int=b //data of the node
   var r:Node=c //right cild
}
def traverse(r:Node):(Node,Node)=(//return a pair
        //get smallest known element
        if(r.l==null) r //smallest is identity if left child is null
        else { //sethighest of traverse of left child as left child
           val y=traverse(r.l)
           r.l=y._2 //left child is highest of traverse left child
           y._2.r=r //and right of this is me
           y._1 //return the currently smallest known element (maybe allways the smallest?
        },
        //get highest known element
        if(r.r==null) r //if right is null, current node is the highest known
        else {
           val y=ttraverse(r.r) //traverse right child
           r.r=y._1 //set pointers for list
           y._1.l=r
           y._2 //return most right child of right child
        }
)//end of return pair
def traverseWrapper(r: Node)=t(r)._1 //just return the smallest element

```

Note that the list is now double linked, it is possible to ignore the back links and save characters (but this is too ugly).

Bring my first and second semester labs back to mind ;-)

# Answer
> 1 votes
# C: 79 114

I'm not sure exactly how this is supposed to be scored, so if someone thinks that other parts of my code should be counted as well, please say so.

Here's the function that does the conversion:

```
t*f(t*n,t*h){static t*p=0;n?f(n->l,h),(p?(n->l=p),p->r=n:(h=n)),p=n,f(n->r,h):0;t*r=h;for(;r->l;r=r->l);return r;}

```

This is the `struct` that I use to represent a tree:

```
typedef struct n {
        int o;
        struct n* l;
        struct n* r;
} t;

```

You can see the rest of the code that I used to test it here (re-compile it, it uses STDIN). Here's a sample run:

```
$ ./tree2list < in
Insert nodes to tree:
Tree traversal:
-527
-7
0
2
3
6
8
23
63
conversion done
List traversal:
-527
-7
0
2
3
6
8
23
63

```

The contents of the file `in`:

```
6
8
2
3
0
-7
23
63
-527

```

I used code from here to help me fix my conversion algorithm.

Edit: I didn't notice that we're supposed to return a pointer to the list, so I still need to fix that. Fixed.

# Answer
> 1 votes
# Haskell: 96

In this solution, new nodes are created, which violate the first rule. However, creating new nodes seems unavoidable in pure functional style code.

```
data N=N Int N N|L
f L=[]
f(N v l r)=f l++v:f r
g _[]=L
g p(x:y)=n where n=N x p$g n y
t=g L .f

```

## Ungolfed Version

```
data Node = Node Int Node Node | Leaf

flatten :: Node -> [Int]
flatten Leaf = []
flatten (Node value left right) = flatten left ++ [value] ++ flatten right

link :: Node -> [Int] -> Node
link _ [] = Leaf
link prev (x:xs) = node where
    node = Node x prev $ link node xs

transform = link Leaf . flatten

```

### Some code for testing:

```
toList Leaf = []
toList (Node v l r) = v:toList r

toReverseList' Leaf = []
toReverseList' (Node v l r) = v:toReverseList' l

toReverseList node@(Node v l Leaf) = toReverseList' node
toReverseList (Node v l r) = toReverseList r
toReverseList Leaf = []

t = Node 4 (Node 2 (Node 1 Leaf Leaf) (Node 3 Leaf Leaf)) (Node 5 Leaf Leaf)

main = do
    print $ toList $ transform t
    print $ toReverseList $ transform t

```

---
Tags: code-golf, sorting, binary-tree, tree-traversal
---


title: Create a World Cup guessing program

text:
# Question
Title: Create a World Cup guessing program
As you know, the World Cup group stage is over, and from tomorrow the best 16 teams will commence the knockout stage:

* Brazil (BRA)
* Mexico (MEX)
* Netherlands (NED)
* Chile (CHI)
* Colombia (COL)
* Greece (GRE)
* Costa Rica (CRC)
* Uruguay (URU)
* France (FRA)
* Switzerland (SUI)
* Argentina (ARG)
* Nigeria (NGA)
* Germany (GER)
* United States (USA)
* Belgium (BEL)
* Algeria (ALG)

In the knockout stage, after each match the winner gets through to the next round, and the loser goes home (there are no draws). Click here to see more about the knockout stage.

You have been hired by golfbet.com, a new betting website because you are known to be good at both programming and sports betting. Your task is to write a program or function which can guess the winner of a match. Of course, everybody makes different guesses, it doesn't matter as long as your guesses are consistent.

If you don't want to guess, you can use the following guesses:

```
BRA
        BRA
CHI
                BRA
COL
        COL
URU
                        GER
FRA
        FRA
NGA
                GER
GER
        GER
ALG
                                        GER
NED
        NED
MEX
                NED
CRC
        CRC
GRE
                        ARG
ARG
        ARG
SUI
                ARG
BEL
        BEL
USA

```
1. The program has to output the same winner regardless the order of the to teams (the winner of the BRA-CHI match has to be the same as of the CHI-BRA match)
2. If a team loses, it cannot play any more matches. This means for matches that don't take place, you have to indicate so. For example if your program guesses Brazil to win the BRA-CHI match, then CHI-GER has to return "no result", because Chile won't play against Germany. See the link above for schedule.

For the sake of simplicity you don't have to deal with the bronze match (but you can of course).

Your program or function takes two strings as input: the 3-letter country code of the two teams and returns the country code of the winning team (you can use standard input/output, or two function parameters/return value). If the given two teams will not play according to your guesses, you must return something else (this can be anything but the country codes, eg empty string, null, error message). You can assume the input is correct (two different country codes which are in the list).

This is primarily a code-golf, so shortest program in bytes wins. However, nice and tricky solutions are also valuable.

**Example (of course, you can make your own guesses):**

input: BRA CHI output: BRA

input: CHI BRA output: BRA

input: CHI GER output: no result

# Answer
> 6 votes
# Python 2.x - ~~368~~ 283

Interesting challenge. Of course we need to get present rankings from the FIFA. Brazil have the so-called "12th man" as they have home advantage therefore the weighting 12/11.

```
a='BRA CHI COL URU FRA NGA ALG GER MEX NED CRC GRE ARG SUI BEL USA'.split()
d=[1242*12/11,1026,1137,1147,913,640,858,1300,882,981,762,1064,1175,1149,1074,1035]
m={}
for n in[16,8,4,2]:
 j=0
 for k in range(0,n,2):
  s=a[k] if d[k]>d[k+1] else a[k+1]
  m[a[k]+' '+a[k+1]]=s
  a[j]=s
  j+=1
def f(s):
 try: print m[s]
 except: print 'no result'

```

Tips to shorten the above are welcome :-).

Improvements thanks to @TheRare and @MrLemon

```
a='BRA CHI COL URU FRA NGA ALG GER MEX NED CRC GRE ARG SUI BEL USA'.split()
d=15,6,10,11,4,0,2,14,3,5,1,8,13,12,9,7
m={}
for n in 16,8,4,2:
 j=0
 for k in range(0,n,2):s=a[k]if d[k]>d[k+1]else a[k+1];m[a[k]+' '+a[k+1]]=s;a[j]=s;j+=1
def f(s):print s in m and m[s]or'no result'

```

This leads to the following results:

```
BRA CHI: BRA
COL URU: URU
FRA NGA: FRA
ALG GER: GER
MEX NED: NED
CRC GRE: GRE
ARG SUI: ARG
BEL USA: BEL
------------
BRA URU: BRA
FRA GER: GER
NED GRE: GRE
ARG BEL: ARG
------------
BRA GER: BRA
GRE ARG: ARG
------------
BRA ARG: BRA

```

Example calls:

```
f('BRA MEX')
no result
f('BRA CHI')
BRA

```

# Answer
> 5 votes
# C, ~~182 178~~ 133 (or 126)

**Not the shortest program here, but it is the shortest in which the prediction can be changed easily. Now that all the semifinalists are known, I'm updating.**

There's some changes to the code, too. Apart from Dennis's suggestions in the comments, the program has been converted to a function (as on re-reading this is allowed by the rules) and the hashing has been shortened.

**Code,133**

```
f(char*a,char*b){
  char*p,*t=" HIAEAIH N?=R=?N ;@4S4@; 5BDGDB5 B@?I?@B",h[3]={*a-a[1]%16,*b-b[1]%16};
  (p=strstr(t,h))&&puts(p-t&2?a:b);
}

```

**How it works**

the inputs `a` and `b` are hashed by the expression `*a-a[1]%16` to a single character (`*a` is a shorter equivalent to `a[0]`). The hash results for teams `a` and `b` are stored in `h`. For example BRA CHI becomes `@;`. Hashed values are as follows (the confirmed semifinalists and my predicted champion are marked with `*`.)

```
GRE E   CRC A   *NED I   MEX H
USA R   BEL =   *ARG ?   SUI N
URU S   COL 4  **BRA @   CHI ;
NGA G   FRA D   *GER B   ALG 5

```

`t[]` stores my predictions. The results of the round of 16 and quarter finals are now known. Each group of 4 teams is ordered such that the 1st and 4th were eliminated, and the 3rd is the semifinalist. Similarly of the semifinalists, I'm predicting that the 1st and 4th will be eliminated and the 3rd semifinalist will be the overall winner. If you disagree with my predictions, simply reorder the table.

The predictions are stored in palindromic blocks to accommodate the possibility of the user entering the teams in either possible order. The ordering puts the winning teams of each set of 4 together to play a third match. Thus in the first group GRE`E` lost to CRC and MEX`H` lost to NED. This sets up CRC`A` to play NED`I` in the quarter final without having to repeat the typing. The string is padded with a space between each group of 4 teams / 7 characters to help ensure there is no output for teams that will not play each other.

The winner of each possible match in each group of 8 characters is as follows: `invalid,b,a,a,b,b,a,invalid`. Thus the correct choice of winner can be made by taking the position of `h` in `t` *AND 2*. Unfortunately the `strstr` function is not the most straighforward as it returns a pointer `p`, so we must subtract `p` from `t` to get the actual position in `t.` If the match is invalid (cannot be found in `t`), `p` is zero and the phrase `no result` is printed.

**Some dubious improvements, 126**

2 characters saved by an improved hash expression. Unfortunately, this requires the case of the teams to be as shown in the test program below the function (eg `Bra` instead of `BRA` as used in the program above.) I've satisfied myself that there is no way of doing this with a single operator, so 2 operators and a single-character constant is as good as it gets. Note also that `Uru` maps to `space` so an alternate character `|` is needed to separate the groups of teamcodes.

5 characters saved by eliminating `t` and treating the prediction string as a literal. This means it is impossible to know the address where the string is stored. However, provided it is not stored at zero, we are only interested in `p&2` so the code will work if the address is divisible by 4. (Note that it is not allowed to treat pointer `p` directly as an integer, it must be subtracted from another pointer. I use the pointer `a` so `a` must also be divisible by 4.) One can be fairly confident on a 32 or 64 bit compiler/architecture strings will be stored in this way. This has been working fine for me on GCC/cygwin, though it refuses to compile on visual studio / windows.

```
g(char*a,char*b){
  char*p,h[3]={*a^a[1]+3,*b^b[1]+3};
  (p=strstr("|%&626&%|+4*#*4+|(71 17(|./3$3/.|/74&47/",h))&&puts(p-a&2?a:b);
}

main(){
  char team[16][4]={"Gre","Crc","Ned","Mex", "Usa","Bel","Arg","Sui", "Uru","Col","Bra","Chi", "Nga","Fra","Ger","Alg"};
  int i;
  for(i=1;i<16;i++){printf("%s %s \n",team[i-1],team[i]);g(team[i],team[i-1]);g(team[i-1],team[i]);}
}

```

# Answer
> 3 votes
## JavaScript 215 206 120  116

A lot of room for improvement:

**ES5 - 215**

```
a=prompt().split(' ');("BRACHI0COLURU0FRANGA0GERALG0NEDMEX0CRCGRE0ARGSUI0BELUSA0BRACOL0FRAGER0NEDCRC0ARGBEL0BRAGER0NEDARG0BRANED".split(0).filter(function(x){return x.match(a[0])&&x.match(a[1])})[0]||"").substr(0,3)

```

**ES6 - 206**

```
a=prompt().split(' ');("BRACHI0COLURU0FRANGA0GERALG0NEDMEX0CRCGRE0ARGSUI0BELUSA0BRACOL0FRAGER0NEDCRC0ARGBEL0BRAGER0NEDARG0BRANED".split(0).filter((x)=>{return x.match(a[0])&&x.match(a[1])})[0]||"").substr(0,3)

```

**Regex Approach - 116**

Thanks to ɐɔıʇǝɥʇuʎs for posting this link, it helped me making the regex

```
a=prompt().split(' ').sort();a.join('').match(/LG(.R(A|G)|GE)|RG(S|BE|CR)|ELUS|AC(H|O)|OLUR|CGR|CM|FRANG|XNE/)&&a[0]

```

# Answer
> 2 votes
# Python (~~179~~ ~~148~~ 139 c.q. way too long)

```
f=lambda *l:sorted(l)[0]if"".join(sorted(l))in"BRACHI COLURU FRANGA ALGGER MEXNED CRCGRE ARGSUI BELUSA BRACOL ALGFRA CRCMEX ARGBEL BRAFRA CRCMEX ARGBEL BRAFRA ARGCRC ARGBRA"else 0

```

Everybody knows the country with the name that comes first in the alphabet is going to win. (This answer just exists to get things started)

Thanks to the charity of the guy(s) over here, I could shorten my answer by a bit:

```
import re;f=lambda *l:sorted(l)[0]if re.match('RGB|CM|RGS|CGR|L.F|XNE|EL.S|O.UR|RGCR|B.AF|L.GE|^BRACHI$|^FRANGA$|^BRACOL$',"".join(sorted(l)))else 0

```

This does assume valid teams, but doesn't need a valid line-up (`f('BRA','NED')` would return 0 (invalid match), but `f('XNE')` would return `'XNE'`. I don't get from your question that this is a problem though. Feel free to re-abuse this regex as you see fit.

Thanks @Ventero, I know nothing about regexes.

```
import re;f=lambda*l:sorted(l)[0]if re.match('RGB|CM|RGS|CGR|L.F|XNE|EL.S|O.UR|RGCR|B.AF|L.GE|BRACHI|FRANGA|BRACOL',"".join(sorted(l)))else 0

```

# Answer
> 2 votes
# Scala (150)

```
type s=String;var m=Map[s,s]();def f(x:(s,s))={var a=x._1;var b=x._2;if(b<a){b=a;a=x._1};if(m.getOrElse(a,a)=="")m.getOrElse(b,b)else{m=m+(b->"");a}}

```

Here are matches between "foo" and "bar" possible, also teams wich won't play in real against each other in the first rounds will have a result.(for example starting with BRA,ARG)

It's just recording loosing teams.

```
type s=String //just aliasing for saving characters
var m=Map[s,s]() //map for storing loosing teams, a set would do too
def f(x:(s,s))={
  var a=x._1 var b=x._2
  if(b<a){b=a;a=x._1};//swap if b<a lexographically
  if(m.getOrElse(a,a)=="")//if a has loosed previously
     m.getOrElse(b,b)// return b if b was not in the map else return ""
  else{
    m=m+(b->"") //add b to the map, because a will definitly win this amazing match
    a //and return a
  }
}

```

Called with:

```
f(("GER","BRA"))

```

# Answer
> 2 votes
# PowerShell (261 221)

```
$a=Read-Host;$b=Read-Host;$x="CHIBRA","URUCOL","FRANGA","ALGGER","MEXNED","CRCGRE","SUIARG","BELUSA";0..($x.Length-2)|%{$x+=$x[2*$_].Substring(3)+$x[2*$_+1].Substring(3)};$x|?{"$a$b","$b$a"-eq$_}|%{$_.Substring(3);exit};0

```

As a relatively new PowerShell user, I find the pipeline absolutely amazing. I think next up might be to try and fiddle with the array to hopefully eliminate all these substring calls. (I had to add a call at the end or else it outputted both teams)

> New member, first attempt at code golf!
>
> Could have hard-coded the quarterfinal, semis, and finals to save a few characters, but \>that wouldn't be quite as fun.
>
> Should be simple enough to decipher, but it fulfills both conditions: gives same winner \>regardless of order entered, and only returns a winner for matches that actually take \>place!
>
> Any advice for improvement would be greatly appreciated, thanks!

### Original

```
$a=Read-Host;$b=Read-Host;$x=("CHIBRA","URUCOL","FRANGA","ALGGER","MEXNED","CRCGRE","SUIARG","BELUSA");for($c=0;$c-lt$x.length-1;$c+=2){$x+=$x[$c].Substring(3)+$x[$c+1].Substring(3)}foreach($i in $x){if($i-match$a-and$i-match$b){return $i.Substring(3)}}return 0

```

# Answer
> 2 votes
# CJam, ~~64~~ 58 bytes

```
lS/$_0=\:+4b256b1>:ca"oM-YtM-mM-^@}gM-^VM-^U8tM-=nM-^MfM-]oM-xgM-)tM-|m@gim{g_"2/&,*

```

The above uses caret and M- notation, since the code contains unprintable characters.

At the cost of six additional bytes, those characters can be avoided:

```
lS/$_0=\:+4b95b1>32f+:c"I8Vyv)2~N{VIEh1$IW32W)B82QBs2G"2/N*\#W>*

```

Try it online.

### Test run

```
$ base64 -d > worldcup.cjam <<< \
> bFMvJF8wPVw6KzRiMjU2YjE+OmNhIm/ZdO2AfWeWlTh0vW6NZt1v+GepdPxtQGdpbXtnXyIyLyYsKg==
$ wc -c worldcup.cjam
58 worldcup.cjam
$ for A in ALG ARG BEL BRA CHI COL CRC FRA GER GRE MEX NED NGA SUI URU USA; do
> for B in ALG ARG BEL BRA CHI COL CRC FRA GER GRE MEX NED NGA SUI URU USA; do
> [[ $A < $B ]] && echo $A - $B : $(LANG=en_US cjam worldcup.cjam <<< "$A $B")
> done; done | grep ': .'
ALG - ARG : ALG
ALG - BRA : ALG
ALG - FRA : ALG
ALG - GER : ALG
ARG - BEL : ARG
ARG - CRC : ARG
ARG - SUI : ARG
BEL - USA : BEL
BRA - CHI : BRA
BRA - COL : BRA
COL - URU : COL
CRC - GRE : CRC
CRC - MEX : CRC
FRA - NGA : FRA
MEX - NED : MEX

```

### How it works

```
lS/$    " Read one line from STDIN, split at spaces and sort the resulting array.         ";
_0=\    " Extract the first element of a copy of the array and swap it with the array.    ";
:+      " Concatenate the strings.                                                        ";
4b      " Convert the resulting string into an integer by considering it a base 4 number. ";
256b    " Convert the integer into an array by considering it a base 256 number.          ";
1>:ca   " Drop the first element, convert into a string and create a singleton array.     ";
"…"     " Push a string of all matches encoded as explained above.                        ";
2/      " Split the string into an array of two-character strings.                        ";
&       " Intersect the two arrays. If the array is non-empty, the teams play.            ";
,*      " Multiply the string on the stack by the length of the array.                    ";

```

# Answer
> 2 votes
# CJam, ~~49~~ 48 bytes

```
lS/$_0="^\16@&^^/+(^]^W^Y,>O?"{_2%+}3*@{2b91%c}%#1&!*

```

The above uses caret notation, since the code contains unprintable characters.

At the cost of two additional bytes, those characters can be avoided:

```
lS/$_0="(=BL2*;74)#%8J[K"{_2%+}3*@{2b91%C+c}%#1&!*

```

Try it online.

### Test run

```
$ base64 -d > wc.cjam <<< bFMvJF8wPSIcMTZAJh4vKygdFxksPk8/IntfMiUrfTMqQHsyYjkxJWN9JSMxJiEq
$ wc -c wc.cjam
48 wc.cjam
$ for A in ALG ARG BEL BRA CHI COL CRC FRA GER GRE MEX NED NGA SUI URU USA; do
> for B in ALG ARG BEL BRA CHI COL CRC FRA GER GRE MEX NED NGA SUI URU USA; do
> [[ $A < $B ]] && echo $A - $B : $(cjam wc.cjam <<< "$A $B"); done; done | grep ': .'
ALG - ARG : ALG
ALG - BRA : ALG
ALG - FRA : ALG
ALG - GER : ALG
ARG - BEL : ARG
ARG - CRC : ARG
ARG - SUI : ARG
BEL - USA : BEL
BRA - CHI : BRA
BRA - COL : BRA
COL - URU : COL
CRC - GRE : CRC
CRC - MEX : CRC
FRA - NGA : FRA
MEX - NED : MEX

```

### Background

We start by assigning and ASCII character to each team by considering its name a base 2 number, taking the resulting integer modulo 91, adding 12 (to avoid unprintable characters) and selecting the character corresponding to the resulting ASCII code. In CJam code, this is achieved by `2b91%c`.

For example, the character codes of `ALG` are `65 76 71`. Since `(4 × 65 + 2 × 76 + 71) = 483`, `483 % 91 + 12 = 40` and 40 if the character code of `(`.

This gives the following mapping:

```
ALG (    ARG 4    BEL #    BRA 2    CHI *    COL ;    CRC 8    FRA B
GER =    GRE J    MEX [    NED K    NGA L    SUI )    URU 7    USA %

```

Now, we can encode the matches of the round of 16 as follows:

```
(=BL2*;74)#%8J[K

```

If we assume that the first team in alphabetical order always wins, the matches of the quarter-finals are as follows:

```
(B2;4#8[

```

Note that this string can be obtained from the first by selecting every second character, starting with the first. In CJam code, this is achieved by `2%`.

Using the same idea, the matches of the semi-finals and the final match are as follows:

```
(248
(4

```

The code

```
"(=BL2*;74)#%8J[K"{_2%+}3*

```

pushes the string containing the matches of the round of 16, then does the following thrice: duplicate the string, extract every second character of the copy, concatenate. The result is the string

```
(=BL2*;74)#%8J[K(B2;4#8[(B2;4#8[(248(B2;4#8[(248(248(4

```

which contains all matches (some of them more than once).

### How it works

```
lS/$        " Read one line from STDIN, split at spaces and sort the resulting array.     ";
_0=         " Extract the first element of a copy of the array.                           ";
"…"         " Push the string containing the matches of the round of 16.                  ";
{_2%+}3*    " Push the remaining matches.                                                 ";
@           " Rotate the input array on top of the stack.                                 ";
{2b91%C+c}% " Perform the mapping for each team in the input array.                       ";
#           " Push the index of the match in the array of all matches (-1 for not found). ";
1&!         " Push 1 if the index is even (valid match) and 0 if it is odd.               ";
,*          " Repeat the string on the stack that many times.                             ";

```

# Answer
> 0 votes
# JavaScript 271

```
t=prompt('Match?').split('-')
x=t[0],y=t[1],T='BRACHICOLURUFRANGAGERALGNEDMEXCRCGREARGSUIBELUSA'
v='\n',R='',W='No Game'
for(z=1;T!='USA';++z,T=n){R+=v+z+v,n='',r=/(...)(...)/g
while(m=r.exec(T))a=m[1],n+=b=m[2],R+=a+'-'+b+v,W=a==x&&b==y||a==y&&b==x?b:W
}
alert(W+'\n'+R)

```

---
Tags: code-golf
---


title: “Disprove” Fermat's Last Theorem

text:
# Question
Title: “Disprove” Fermat's Last Theorem
Write a program, in the language of your choice, that *appears* to successfully find a counterexample to Fermat's Last Theorem. That is, find integers *a*, *b*, *c* \> 0 and *n* \> 2 such that an \+ bn = cn.

Of course, you can't *really* do it, unless there's a flaw in Andrew Wiles' proof. I mean *fake it*, by relying on

* integer overflow
* floating-point rounding error
* undefined behavior
* data types with unusual definitions of addition, exponentiation, or equality
* compiler/interpreter bugs
* or something along those lines.

You may hard-code some or all of the variables `a`, `b`, `c`, or `n`, or search for them by doing loops like `for a = 1 to MAX`.

This isn't a code golf; it's a contest to find clever and subtle solutions.

# Answer
> 57 votes
## J

Actually, Fermat did make quite a blunder: It's actually wrong for any b, c or n if a is 1:

```
   1^3 + 4^3 = 5^3
1
   1^4 + 5^4 = 11^4
1
   1^9 + 3^9 = 42^9
1

```

> Maybe just maybe, Fermat's precedence rules weren't strictly right to left.

# Answer
> 36 votes
# TI-Basic

```
1782^12+1841^12=1922^12

```

Output (true)

```
1

```

# Answer
> 35 votes
# Java

This Fermat guy must have been sleeping. I get hundreds of solutions to the equations. I merely converted my Excel formula to a Java program.

```
public class FermatNoMore {
    public static void main(String[] args) {
        for (int n = 3; n < 6; n++)
            for (int a = 1; a < 1000; a++)
                for (int b = 1; b < 1000; b++)
                    for (int c = 1; c < 1000; c++)
                        if ((a ^ n + b ^ n) == (c ^ n))
                            System.out.println(String.format("%d^%d + %d^%d = %d^%d", a, n, b, n, c, n));
    }
}

```

> The `^` operator actually means XOR in Java, as opposed to exponentiation in typical plain-text

# Answer
> 19 votes
## C++

```
#include <cstdlib>
#include <iostream>

unsigned long pow(int a, int p) {
  unsigned long ret = a;

  for (int i = 1; i < p; ++i)
    ret *= a;

  return ret;
}

bool fermat(int n) {
  // surely we can find a counterexample with 0 < a,b,c < 256;
  unsigned char a = 1, b = 1, c = 1;

  // don't give up until we've found a counterexample
  while (true) {
    if (pow(a, n) + pow(b, n) == pow(c, n)) {
      // found one!
      return true;
    }

    // make sure we iterate through all positive combinations of a,b,c
    if (!++a) {
      a = 1;
      if (!++b) {
        b = 1;
        if (!++c)
          c = 1;
      }
    }
  }

  return false;
}

int main(int argc, char** argv) {
  if (fermat(std::atoi(argv[1])))
   std::cout << "Found a counterexample to Fermat's Last Theorem" << std::endl;
}

```

Compiled with `clang++ -O3 -o fermat fermat.cpp`, tested with `Ubuntu clang version 3.4.1-1~exp1 (branches/release_34) (based on LLVM 3.4.1)`:

```
./fermat 3
Found a counterexample to Fermat's Last Theorem

```

We obviously found a, b, c \> 0 so that a3 \+ b3 = c3 (this also works for n = 4, 5, 6, ...).

> Printing a, b and c might prove a bit difficult though ...

# Answer
> 13 votes
# Java

It looks like the theorem holds for n=3, but I found counterexamples for n=4:

```
public class Fermat {
    public static int p4(final int x) {
        return x * x * x * x;
    }

    public static void main(final String... args) {
        System.out.println(p4(64) + p4(496) == p4(528));
    }
}

```

Output:

```
true

```

Explanation:

> Even if the numbers seem small, they overflow when raised to the 4th power. In reality, 644 \+ 4964 = 5284 \- 234, but 234 becomes 0 when restricted to int (32 bits).

# Answer
> 9 votes
# Python

```
import math
print math.pow(18014398509481984,3) + math.pow(1, 3) \
      == math.pow(18014398509481983,3)

```

> Who says that *c* must be greater than *a* and *b*?

# Answer
> 5 votes
# GolfScript

```
# Save the number read from STDIN in variable N and format for output.

:N"n="\+

{
  [{100rand)}3*] # Push an array of three randomly selected integers from 1 to 100.
  .{N?}/         # Compute x**N for each of the three x.
  +=!            # Check if the sum of the topmost two results equals the third.
}{;}while        # If it doesn't, discard the array and try again.

# Moar output formatting.

~]["a=""\nb=""\nc="""]]zip

```

This approach finds a bunch of different solutions. For example:

```
$ golfscript fermat.gs <<< 3
n=3
a=43
b=51
c=82

```

### How it works

> The first line should start with a `~` to interpret the input. Instead of, e.g., the number 3 , variable `N` contains the string `3\n`.
> While `2 3 ?` calculates 3, `2 N ?` pushes the index of a character with ASCII code 2 in `N` (-1 for not found).
> This way, `43 N ?` and `82 N ?` push `-1` and `51 N ?` pushes `0` (51 is the ASCII character code of `3`).
> Since `-1 + 0 = -1`, the condition is satisfied and `(43,51,82)` is a "solution".

# Answer
> 4 votes
# C

Well of course you folks are all finding counterexamples, you keep on getting integer overflows. Plus, you're being really slow by iterating on c as well. This is a much better way to do it!

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

int main(void) {
  double a, b, c;
  for (a = 2; a < 1e100; a *= 2) {
    for (b = 2; b < 1e100; b *= 2) {
      c = pow(pow(a, 3) + pow(b, 3), 1.0/3);
      if (c == floor(c)) {
        printf("%f^3 + %f^3 == %f^3\n", a, b, c);
      }
    }
  }
  return 0;
}

```

> `double` might be great on the range, but it's still a bit lacking in precision...

# Answer
> 4 votes
# C

We all hate integer overflows, so we'll use a small exponent `n` and some floating point conversions. But still the theorem would not hold for `a = b = c = 2139095040`.

```
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

int a, b, c;
int n;

int disprove(int a, int b, int c, int n)
{
    // Integers are so prone to overflow, so we'll reinforce them with this innocent typecast.
    float safe_a = *((float *)&a);
    float safe_b = *((float *)&b);
    float safe_c = *((float *)&c);

    return pow(safe_a, n) + pow(safe_b, n) == pow(safe_c, n);
}

int main(void)
{
    srand(time(NULL));

    a = b = c = 2139095040;
    n = rand() % 100 + 3;

    printf("Disproved for %d, %d, %d, %d: %s\n", a, b, c, n, disprove(a, b, c, n) ? "yes" : "no");
}

```

Output:

`Disproved for 2139095040, 2139095040, 2139095040, 42: yes`

`Disproved for 2139095040, 2139095040, 2139095040, 90: yes`

> In IEEE 754, the number 2139095040, or 0x7F800000, represents positive infinity in single-precision floating point types. All `pow(...)` calls would return +Infinity, and +Infinity equals +Infinity. An easier task would be to disprove the Pythagorean theorem by using 0x7F800001 (Quiet NaN) which is not equal to itself according to the standard.

# Answer
> 2 votes
# Javascript

```
var a, b, c, MAX_ITER = 16;
var n = 42;
var total = 0, error = 0;

for(a = 1 ; a <= MAX_ITER ; a++) {
  for(b = 1 ; b <= MAX_ITER ; b++) {
    for(c = 1 ; c <= MAX_ITER ; c++) {
      total++;
      if(Math.pow(a, n) + Math.pow(b, n) == Math.pow(c, n)) {
        error++;
        console.log(a, b, c);
      }
    }
  }
}

console.log("After " + total + " calculations,");
console.log("I got " + error + " errors but Fermat ain't one.");

```

42 is magic, you know.

```
> node 32696.js
After 2176 calculations,
I got 96 errors but Fermat ain't one.

```

And also Wiles ain't one.

> Javascript `Number` is not big enough.

# Answer
> 2 votes
# T-SQL

To disprove this Fermat guy's theorem, we just need to find a counter example. It seems, he was super lazy, and only tried it for really small permutation. In fact, he wasn't even trying. I found a counter example in just 0 \< a,b,c \< 15 and 2 \< e \< 15. Sorry I'm a golfer at heart so I'll ungolf this code later!

```
with T(e)as(select 1e union all select (e+1) from T where e<14)select isnull(max(1),0)FROM T a,T b,T c,T e where e.e>2 and power(a.e,e.e)+power(b.e,e.e)=power(c.e,e.e)

```

Returns 1, meaning we found a counter example!

> The trick is that while the first e looks like an alias, it actually is a sneaky way of changing the data type of e from an int to a floating point type equivalent to a double. By the time we got to 14 we are beyond the precision of a floating point number so we can add 1 to it and we still don't lose anything. The minification is a nice excuse to explain away my seemingly silly double declaration of a column alias in the rcte. If I didn't do this it would overflow long before we got to 14^14.

# Answer
> 1 votes
## JavaScript

It appears this guy was onto something alright. Onto drugs if you ask me. Given the constraints, no set of values can be found for which the theorem holds true.

```
var a = 1,
    b = 1,
    c = 1,
    n = 3,
    lhs = (a^n + b^n),
    rhs = c^n;

alert(lhs === rhs);

```

> As in Java, the `^` operator is the bitwise XOR operator in JavaScript. The correct way to calculate the power of a number is to use Math.pow.

# Answer
> 0 votes
# Another BASIC counterexample

```
10 a = 858339
20 b = 2162359
30 c = 2162380
40 IF (a^10 + b^10) = c^10 THEN
50   PRINT "Fermat disproved!"
60 ENDIF

```

---
Tags: popularity-contest, math, underhanded
---