title: Code me a cookie

text:
# Question
Title: Code me a cookie
## Challenge

Code an ASCII cookie of a kind according to the input.

## Input

* The cookie kind. This is one of the three strings: "Plain", "Chocolate", or "Nuts". May be function arguments, stdin (or closest equivalent), or file arguments.

## Output

* An ASCII cookie. See below.

Must be

```
     ___
    /   \
    |   |
    \___/

```

for Plain input,

```
     ___
    /. .\
    | . |
    \___/

```

for Chocolate input, and finally

```
     ___
    /^  \
    |^ ^|
    \___/

```

for Nut input.

## Other information

* This is my first challenge, it's as simple as can be. Constructive feedback is greatly appreciated.
* Use any means to do so.
* Trailing spaces are fine.
* This is a code golf challenge, so shortest entry at the end of 9 days (Wednesday, the 12th of August 2015) wins.

## Thank you!

The winner is Jakube using Pyth with 41 bytes. Thank you to all who participated. I will now task myself with coming up with more complicated challenges.

# Answer
> 4 votes
# Pyth, ~~42~~ 41 bytes

```
X" ___
/d a\\
|cac|
\___/"G.>"^X .  .^"Cz

```

Try it online: Regular Input / Test Suite

### Explanation:

```
 "..."                      template string
X     G                     replace "a..z" in ^ with:
                   Cz         convert z to an integer (base 256 of ord(char))
       .>"^X .  .^"           rotate "^X .  .^"
                              ["Plain"     -> " .  .^^X",
                               "Chocolate" -> ".  .^^X ",
                               "Nuts"      -> " .^^X . "]

```

# Answer
> 7 votes
# Ruby, 73

```
->s{' ___
/'+['^  \
|^ ^','. .\
| . ','   \
|   '][s[0].ord%3]+'|
\___/'}

```

This is an anonymous lambda function. Here it is in a test program:

```
g=->s{' ___
/'+['^  \
|^ ^','. .\
| . ','   \
|   '][s[0].ord%3]+'|
\___/'}

puts g.call(gets)

```

It just uses the first letter of the cookie type (in uppercase) and takes it modulo 3 to get an index in the range `0..2`. Then it returns the string representing the cookie, with the appropriate strings embedded in the right places.

# Answer
> 4 votes
# Python 2.7.6, 99 bytes

```
def c(t):n=hash(t)%3;return" ___\n/"+" ^."[n]+" "+"  ."[n]+"\\\n|"+[" ","^ ^"," . "][n]+"|\n\\___/"

```

This algorithm relies on the fact that `hash(cookie)%3` gives 0 when `cookie = "Plain"`, 1 when `cookie = "Nut` and 2 when `cookie = "Chocolate`. If anyone knows a way to make this code shorter, please let me know in the comments.

# Answer
> 3 votes
# C: 122

```
q(char *p){char *t,*m;int i=*p%3;t=i?i%2?". .":"   ":"^  ";m=i?i%2?" . ":"   ":"^ ^";printf(" ___\n/%s\\ \n|%s|\n\\___/",t,m);}

```

Explanation after i finish golfing.

Example of use:

```
 int main(void){
 q("Plain");
 printf("\n");
 q("Nut");
 printf("\n");
 q("Chocolate");
 }

```

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

```
" ___
/""^  ^ ^. . ."S7*+6/rci=3/"\
|"*"|
\___/"

```

Try it online in the CJam interpreter.

### How it works

```
" ___
/"

e# Push that string.

"^  ^ ^. . ."S7*+6/

e# Push that string, append 7 spaces and split into chunks of length 6.
e# This pushes ["^  ^ ^" ". . . " "      "].

rci

e# Read from STDIN, cast to character, then to integer.
e# "Plain", "Chocolate", "Nuts" -> 'P', 'C', 'N' -> 80, 67, 78

=

e# Select the corresponding element from the array.
e# Arrays wrap around in CJam, so for an array A of length 3,
e# A80= is A2=, A67= is A1= and A78= is A0=.

3/

e# Split into chunks of length 3.

"\
|"*

e# Join those chunks, using that string as separator.

"|
\___/"

e# Push that string.

```

At the end, CJam automatically prints all elements on the stack.

# Answer
> 3 votes
# Javascript (ES6), 90

```
s=>" ___\n/"+(s.length-4?s.length-5?". .\\\n| . ":"   \\\n|   ":"^  \\\n|^ ^")+"|\n\\___/"

```

This is an anonymous arrow function. It uses the length of the input to determine which cookie to draw.

Explanation:

```
s=>
 " ___\n/" +               //build the first part of the cookie

 (s.length - 4 ?           //if the length is 4, this condition will evaluate to 0, which coerces to false. Otherwise it is true

      s.length - 5 ?            //if the length is 5, this evaluates to false; otherwise true

           ". .\\\n| . " :      //build the unique part of the Chocolate cookie, if length was not 5
           "   \\\n|   "        //build the unique part of the Plain cookie, if length was 5

      : "^  \\\n|^ ^"      //build the unique part of the Nuts cookie, if length was 4
 )

 + "|\n\\___/"             //build the last part of the cookie, and implicitly return the built string

```

To test:

```
f=s=>" ___\n/"+(s.length-4?s.length-5?". .\\\n| . ":"   \\\n|   ":"^  \\\n|^ ^")+"|\n\\___/"

console.log(f("Nuts"))
console.log(f("Plain"))
console.log(f("Chocolate"))

```

# Answer
> 3 votes
# BrainFuck, ~~481~~ ~~447~~ 436 bytes

Why not BrainFuck?, the program can probably be golfed more, but I think it's pretty neat.

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

```

# Answer
> 3 votes
**C# With indentation and line break**

```
using System;
class Cookie
{
    static void Main()
    {
      String E="",N="",C=Console.ReadLine();
      if(C=="P"){E="   ";N="   ";}
      if(C=="C"){E=". .";N=" . ";}
      if(C=="N"){E="^  ";N="^ ^";}
      Console.Write(" ___ \n/" + E + "\\ \n|" + N + "|\n\\___/");
    }
}

```

**Golfed (225 Characters)**

```
using System;class X{static void Main(){String E="",N="",C=Console.ReadLine();if(C=="P"){E="   ";N="   ";}if(C=="C"){E=". .";N=" . ";}if(C=="N"){E="^  ";N="^ ^";}Console.Write(" ___ \n/" + E + "\\ \n|" + N + "|\n\\___/");}}[![enter image description here][1]][1]

```

# Answer
> 2 votes
# Pyth, ~~58~~ ~~54~~ ~~53~~ ~~52~~ 50 bytes

```
+d*\_3p+\/j"\\
|"c@["^  ^ ^"*". "3*d6)Chz3\|"\___/

```

I don't think this can be golfed more. I was really trying to squeze this in under 50 bytes

# Answer
> 2 votes
## **C# 6, 105 bytes**

So very nearly got this sub-100 bytes, no idea where to squeeze the last few bytes from though :C

```
string C(string t)=>$" ___\n/{(t[0]=='C'?". .\\\n| . ":t[0]=='N'?"^  \\\n|^ ^":"   \\\n|   ")}|\n\\___/";

```

# Answer
> 2 votes
## JavaScript (ES6), 72 bytes

About as simple as it gets… new lines are counted as 1 byte each.

```
f=s=>` ___
/${s[4]?s[5]?`. .\\
| . `:`   \\
|   `:`^  \\
|^ ^`}|
\\___/`

```

### Demo

As it is ES6, this demo only works in Firefox and Safari for now.

```
f=s=>` ___
/${s[4]?s[5]?`. .\\
| . `:`   \\
|   `:`^  \\
|^ ^`}|
\\___/`

// Snippet stuff

A.innerHTML = f("Nuts");
B.innerHTML = f("Plain");
C.innerHTML = f("Chocolate");
```

```
<p>Nuts</p>
<pre id=A></pre>

<p>Plain</p>
<pre id=B></pre>

<p>Chocolate</p>
<pre id=C></pre>
```

# Answer
> 2 votes
# Commodore 64 BASIC, 181 bytes

```
10 INPUT A$
20 IF A$="PLAIN" THEN B$="/   \":C$="|   |"
30 IF A$="CHOCOLATE" THEN B$="/. .\":C$="| . |"
40 IF A$="NUTS" THEN C$="/^  \":C$="|^ ^|"
50 PRINT" ___":PRINT B$:PRINT C$:PRINT"\___/"

```

Notes:

Instead of backslashes `\` the SHIFT-M characters have been used, for slashes `/` \- SHIFT-N and for pipes `|` \- SHIFT-T. SHIFT-Z (card diamond sign) was used for `^`. In fact characters do not matter as they all occupy one byte each.

Because on C64 each command (PRINT, INPUT, THEN, etc.) takes 2 bytes in memory (or some even one, IIRC), the BASIC language was worth trying (however, it took more bytes than I expected).

The program size was calculated by measuring free memory before typing the program (38909 bytes) and after (38728 bytes), using `PRINT FRE(0)+65536` command, giving 181 bytes of difference.

Code tested and screenshots prepared with this tool: http://codeazur.com.br/stuff/fc64\_final/ (GPL).

Screenshots:

# Answer
> 2 votes
# Lua 5.3, 113 Bytes 112 Bytes

```
c=io.read()print(' ___\n/'..(c=='plain'and'   \\\n|   'or c=='nut'and'^  \\\n|^ ^'or'. .\\\n| . ')..'|\n\\___/')

```

It uses a lot of the ternary operator and string concatenation, and I squeezed out all whitespace that isn't part of the output itself.

# Answer
> 2 votes
## Java 258 217 characters/bytes

---

**Golfed**
```
class C{public static void main(String[] a){p(" ___");if(a[0].equals("Chocolate")) {p("/. .\\");p("| . |");}if(a[0].equals("Nut")){p("/^  \\");p("|^ ^|");}p("\\___/");}static void p(String s) {System.out.println(s);}}

```

***Original***

```
class C {
    public static void main(String[] a) {
        p(" ___");
        if(a[0].equals("Chocolate")) {
            p("/. .\\");
            p("| . |");
        }
        if(a[0].equals("Nut")){
            p("/^  \\");
            p("|^ ^|");
        }
        p("\\___/");
    }
    static void p(String s) {
        System.out.println(s);
    }
}

```

# Answer
> 1 votes
# **LUA 270 characters 270 bytes**

```
    c = io.read()
    if c == "plain" then
    print" ___"
    print"/   \\"
    print"|   |"
    print"\\___/"
    io.read()
    elseif c == "chocolate" then
    print" ___"
    print"/. .\\"
    print"| . |"
    print"\\___/"
    io.read()
    elseif c == "nut" then
    print" ___"
    print"/^  \\"
    print"|^ ^|"
    print"\\___/"
    end

```

# Answer
> 1 votes
## LOLCODE 265 characters

```
HAI
I HAS A T
GIMMEH T
VISIBLE " ___"
BOTH SAEM T AN "Chocolate", O RLY?
YA RLY
VISIBLE "/. .\"
VISIBLE "| . |"
OIC
BOTH SAEM T AN "Nut", O RLY?
YA RLY
VISIBLE "/^ ^\"
VISIBLE "|^  |"
OIC
BOTH SAEM T AN "Plain", O RLY?
YA RLY
VISIBLE "/   \"
VISIBLE "|   |"
OIC
VISIBLE "\___/"
KTHXBYE

```

`Run`

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


title: Efficient error-free* encoding

text:
# Question
Title: Efficient error-free* encoding
## The mission

As is well known, the genetic material of all known creatures on Earth is encoded in DNA; using the four nucleotides adenine, thymine, cytosine, and guanine. (Commonly represented by ATGC).

A bioinformaticist wishing to store an entire genome would of course not want to store this as ASCII, because each choice can be represented by a mere two bits!

## The specification

Your mission, should you choose to accept it, is to write a pair of programs, functions or methods to convert an ASCII representation to a binary representation and back; representing `A` as `b00`, `T` as `b01`, `G` as `b10`, and `C` as `b11` (henceforth "units").

In addition, the high bits of each byte should contain the count of units in the byte, making each byte represent a triplet.

For example: `"GATTACCA"` becomes `b11 100001 b11 010011 b10 1100xx`.

In the ASCII to binary input, spaces, tabs and newlines should be ignored. Any character not in the set of `[ \r\n\tATGC]` is an error and may either be ignored or terminate processing.

In the binary to ASCII input, bytes whose two high bits are `b00` may be ignored.

The ASCII output may contain whitespace; but should never be more than 4 times the size of the binary input plus one byte long, and must end with a newline.

The binary output may contain an arbitrary number of `b00xxxxxx` "control" bytes; but must never be longer than the ASCII input.

Each conversion program must support input of arbitrary length; and should complete the encoding or decoding in approximately linear time.

## The twist

Unfortunately for the bioinformaticist for whom you are performing this task, he has in some way wronged you, on a personal yet perhaps petty level.

Perhaps he went out with your sister once, and never called her again. Perhaps he stepped on your dog's tail. The specifics are not really important.

What is important is that you have a chance for payback!

## The details

Each conversion should introduce a small error rate; on the order of one error per ten thousand to a million units processed.

An error can be one of the following:

* Duplication errors: `"GAT TAC CA"` becomes `"GAT TAA CCA"`
* Deletion errors: `"GAT TAC CA"` becomes `"GAT TAC A"`
* Translation errors: `"GAT TAC CA"` becomes `"GTA TAC CA"`
* Triplet duplications: `"GAT TAC CA"` becomes `"GAT TAC TAC CA"`
* Triplet slippages: `"GAT TAC CA"` becomes `"TAC GAT CA"`
* Triplet reversals: `"GAT TAC CA"` becomes `"GAT CAT CA"`

That errors will be introduced should of course not be immediately obvious from the code; and irrespective of the length of the input; the conversion should introduce at least one error.

Two runs with identical inputs should not *necessarily* produce identical outputs.

## The trick

The vile bioinformaticist is a moderately competent coder; and as such, some constructs will be automatically discovered, and are as such banned:

* He will automatically discover any calls to system random number generators, such as rand(), random(), or reading from /dev/urandom or /dev/random (or whatever the language equivalent is).
* He will also notice any superfluous variables, counters or loops.

## The scoring

The encoder and decoder will be scored individually.

Each will be run 3 times against a set of 100 randomly generated input files, each file with a size on the order of 3 million units.

The data for the encoder test cases will be created approximately as so:

```
for (l = 1 => bigNum)
  for (t = 1 => 20)
    random_pick(3,ATGC)
    t == 20 ? newline : space

```

The data for the decoder test cases will be created approximately as so:

```
for (u = 1 => bigNum)
  for (t = 1 => 20)
    random_byte() | 0b11000000
   0x00

```

### The encoder

* Each byte missing from the expected minimum length in the actual length will score -1 points, up to a maximum of -1000. (The expected minimum length is `ceil(count(ATGC) / 3)`.)

### The decoder

* Each byte over the expected maximum length in the actual length will score -1 points, up to a maximum of -1000. (The expected maximum length is `size(input) * 4 + 1`.)

### Both

* Each kind of error that can be produced will score 100 points; for a total of 600 points possible for each, 1200 total.
* Each test case for which the encoder produces more than 30% more or less errors than its own average will be penalized by -5 points.
* Each test case for which the encoder produces less than 15% more or less errors than its own average will be given 5 points.
* Each test case where all three runs produce identical outputs will be penalized by -10 points.

### Hard requirements

An entry will be disqualified if:

* For any valid input longer than one triplet it fails to produce even one error.
* Its performance is such that it cannot complete the test gauntlet within approximately one hour.
* It on average produces more than one error in every ten thousand units.
* It on average produces less than one error in every million units.

## The interface

The entrants should accept input on the standard input, and output to the standard output.

If the entry is one program with dual function; the switches `-e` and `-d` should set the program for encoding and decoding, respectively.

Example invocations:

```
$ encoder <infile.txt >outfile.bin
$ decoder <infile.bin >outfile.txt
$ recoder -e <infile.txt >outfile.bin

```

## The winner

The winner is the entry with the highest score; the theoretical maximum being 1200 for error kinds plus 3000 points for stability in error generation rate.

In the unlikely event of a draw; the winner will be determined by vote count.

## The additional notes

For the purposes of running the test gauntlet, each entry should include run or compilation instructions.

All entries should preferably be runnable on a Linux machine without X.

# Answer
# Perl 5.10

I'm glad to present my solution in Perl.

When I started the challenge I was quite sure that Perl would stay well below the limit of 1 hour.

For testing purpose I developed a plain sample generator and a coded sample generator.

Then I developed the encoder that took a bigger effort and produced a longer code. The encoder works as follow:

1. first loop reads the whole file and splits data to have an array of all triplets
2. second loop traverses the array and prepend to each element its length
3. third loop traverses again and maps each character to give the output.

The coded binary output is so formatted as new-line terminated "lines" of 20 octets where each octet codes one triplet, with two characters of prefix (like a cyclical line-number).

for example, the *shortest* three byte input:

```
AAA

```

should give the shortest output of three bytes plus new-line.

```
00ÿ

```

that is

```
30 30 FF 0A

```

and

```
AGG CGC AAC GGC TAA ATC GTT TTC ACA CCA CGT TTG AAA CGG GTG ACA CGA GAT TTA GTC
TAT GGT ACT AGG TAC GCC GTG GTG CGT GCG GAG TTA CTA GAT GTG TTA GTA CGC CAT CGT

```

should give the following binary.

```
01ÊûÃëÐÇå×ÌüùÖÀúæÌøáÔç
00ÑéÍÊÓïææùîâÔôáæÔäûñù

```

*Should* because of the small error rate: For the smallest input, the script introduces 1 error.

For a 3 million triplets file run, the encoder introduces 11 errors.

Provided that the script is dnacodec3.pl, the run is invoked at command prompt as usual:

```
$> perl dnacodec3.pl -e < plain.txt > coded.txt

```

The decoder works as follow:

1. first loop reads the whole file and splits data to have an array of all octets. It keep track of every new-line.
2. second loop examines each octet, retaining those not beginning with 00 and disregards the rest. The plain Ascii output is formatted as new-line terminated lines of triplets separated by one space. The new-line are in the *same* position as they were in the input.

I prepared a 3 million triplets sample test file (about 12MByte) and tested for timing. Using my laptop with an Intel Core i5 vPro at 2.6 GHz, the 3M encoder run always takes less than 20 sec. During the run it takes 200-220 MByte of RAM. What a waste!

The decode run takes less than 10 sec. It cannot introduce errors... for now.

Again, for the decoding run

```
$> perl dnacodec3.pl -d < coded.txt > plain.txt

```

Here is the code

```
#!/usr/bin/perl
use strict ;
use warnings ;
my $switch = shift || die "usage $0 [-e|-d]\n";
my %map = qw( x 10  X 11  c 0b  ? 00
              A 00  T 01  G 10  C 11
              0 00  1 01  2 10  3 11
              00 A  01 T  10 G  11 C  ) ;
my $r = 20 ;
my @dummy = unpack ( '(A4)*', '0xxx' x $r ) ;
my $map = oct( $map{ c } . ($map{ C } x 9) ) ;
my $t = time() ;
my @inp = () ;
my @out = () ;
my @buf = () ;
my $n ;

sub arch {
    push @buf, @dummy[ 0 .. $r - $#buf - 2 ] ;
    push @out, "@buf" ;
    @buf = () ;
}

sub encode {
    my $mask = '(A3)*' ;
    while ( my $row = <STDIN> ) {
        chomp $row ;
        $row =~ s/\s+//g ;
        $row =~ s/[^\r\n\tATGC]//g ;
        next unless $row ;
        my @row = unpack( $mask, $row ) ;
        push @inp, @row if $row ;
    }
    $n = scalar @inp ;
    $r = $n if $r > $n ;
    for ( my $i = $n - 1 ; $i >= 0 ; --$i ) {
        my $e = $inp[$n-$i-1] ;
        my $l = length( $e ) ;
        my $d = $e =~ /\?/? 0: $l ;
        push @buf, ( $d -((($i-($n>>1))&$map)?0:1) )
           . $e . 'x'x(3-$l) ;
        arch unless $i % $r ;
    }
    arch if scalar @buf ;
    my $m = scalar @out ;
    for ( my $j = $m - 1 ; $j >= 0; --$j ) {
        my @ary = () ;
        my $e = $out[$m-$j-1] ;
        for my $byte ( split / /, $e ) {
            my @byte = split ( //, $byte ) ;
            my @trad = map { $map{ $_ } } @byte ;
            my $byte = join( '', @trad ) ;
            push @ary, $byte ;
        };
        my $row = sprintf( '%02d', $j % $r) ;
        $row .= pack( '(B8)*', @ary ) ;
        print "$row\n" ;
    }
}

sub decode {
    my $mask = '(B8)*' ;
    while ( my $row = <STDIN> ) {
        chomp $row ;
        next unless $row ;
        my @row = unpack( $mask, $row ) ;
        push @inp, @row[0..$#row], '?' if $row ;
    }
    $n = scalar @inp ;
    my @ary = () ;
    for ( my $i = $n - 1 ; $i >= 0 ; --$i ) {
        my $e = $inp[$n-$i-1] ;
        if ( $e ne '?' ) {
            my $u = oct( '0b'. substr($e,0,2) ) ;
            my $a = '' ;
            for my $j ( 1 .. $u ) {
                $a .= $map{ substr($e,$j+$j,2) } ;
            }
            push @ary, $a if $u ;
        }
        else {
            my $row = "@ary" ;
            $row =~ s/\s{2,}//g ;
            print "$row\n" if $row ;
            @ary =() ;
        }
    }
}

decode if $switch eq '-d' ;
encode if $switch eq '-e' ;

```

And here is the sample generator:

```
sub test_coder {
    my $n = shift || 1000 ;
    my @b = qw( A C G T ) ;
    for (my $l = 0; $l < $n; $l++) {
        my @ary = () ;
        for (my $t = 0; $t < 20; $t++) {
            push @ary, $b[ int(rand(4)) ] . $b[ int(rand(4)) ] . $b[ int(rand(4)) ] ;
        }
        print "@ary\n" ;
    }
    1;
}

sub test_decoder {
    my $n = shift || 1000;
    for (my $l = 0; $l < $n; $l++) {
        my @ary = () ;
        for (my $t = 0; $t < 20; $t++) {
            push @ary, int(rand(256)) | 0b11000000 ;
        }
        my $row = pack( 'C*', @ary ) ;
        print "$row\000" ;
    }
    1;
}

test_coder( @ARGV ) if $switch eq '-g' ;
test_decoder( @ARGV )  if $switch eq '-h' ;

```
> 3 votes

---
Tags: code-challenge, restricted-source, underhanded
---


title: Arithmetic... tock... tick... tock

text:
# Question
Title: Arithmetic... tock... tick... tock
*This question brought to you by a game I like to play when stuck in long phone meetings.*

Given any two times from a 24 hour clock (from 00:00 to 23:59), how many valid mathematical equations can be generated with all of the times in between using only basic arithmetic operations?

**Input:** two four digit strings (no colon) representing valid times in a 24 hours cycle.

**Examples:**

For input=0000, 1300

```
03:26 produces: "0+3*2=6" and "03*2=6" etc.
11:10 produces quite a few, including: "1*1=1+0" and "1=1=1^0" and  "1=11^0" etc.
12:24 produces: "1/2=2/4" and "1=(2*2)/4" etc.

```

**Valid operations are:**

* addition
* subtraction
* multiplication
* division (floating point)
* exponentiation
* factorial

**Other allowable symbols**

* Parentheses
* Equal signs

Shortest code wins.

**Notes**

* The goal is to find the *number* of valid expressions between two times, not the number of times that *contain* a valid expression.
* The two times given as input are included in the range of times.
* You may group the digits in any way possible, so "1223" can be "12 23" or " 1 2 23" or "1 223" etc. etc.
* You may use as many parentheses as needed.
* You may use more than one `=` sign. For instance, the time `11:11` has the valid expression `1=1=1=1`.
* If the first time occurs chronologically after the second time, the range of times should wrap as if crossing into the next day.
* The numbers must remain in their original order- you may not re-order the digits.
* When clustering numbers, zero's may absolutely be the front most digit, in which case, they are ignored ("0303" clustered as "03 03" is just two digits with the value of 3.)
* You MAY NOT use the minus sign as unary negation. Therefore, "12:01" does NOT produce "1-2=-(01)", but DOES produce "1-2=0-1".
* You MAY NOT add decimal points to digits. Therefore, "12:05" does NOT produce "1/2=0.5".
* No chaining of factorials- a digit may be followed by at most one "!", no more, otherwise, many times would have infinite solutions. Ex: "5!" is valid but "5!!" is not valid.

# Answer
# Python3, 363 chars

Since no answer is given till today, I hand in what I got. Sadly, the try/except block is too fat, I didn't found a way to save chars there. It is really tricky with the nested loops there, not all can be done with list comprehensions I think, but maybe someone can tell me how.

However, I restricted the challenge myself to only use basic math '+-\*/' and no parentheses.

```
a,b = input().split()
r=0
for time in [c for c in range(int(a),int(b)) if c/10%10<6]:
 t,*ts='%04d'%time
 e=[t]
 for d in ts:
  e=[(n+o+d,n+d)[o==' '] for o in ' -+*/=' for n in e]
 for h in [g for g in [e.split('=') for e in e if '='in e] if len(g)>1]:
  for k in h:
   try:
    if eval(h[0]) != eval(k):
     break
   except:
    break
  else:
   r+=1
print(r)

```

My full code (hope something explanatory) on this CodeGolf can be found on my pastebin.
> 2 votes

---
Tags: code-golf, expression-building, clock
---


title: Print a non-clashing binary search tree

text:
# Question
Title: Print a non-clashing binary search tree
## Brief

* Print an ASCII representation of a binary search tree.
* You should write your own minimum implementation logic of a BST (node, left, right, insert)

```
(50,30,70,20,80,40,75,90) gives:

__50__70__80__90
   |       |
   |       |__75
   |
   |__30__40
       |
       |__20

```

## Detailed requirements

* Items are inserted into the tree in the order in which they are in the list
* All node values are right aligned in columns.
* Right nodes are joined using `__`
* Right nodes are represented along the horizontal and appear directly to the right of the parent node
* Right nodes are separated by a minimum of 2 underscores (\__)
* Left nodes are joined using `|` and `|__` on the next line
* Left nodes are represented along the vertical and appear under and to the right of the parent (ie, next column).
* Left nodes are separated by a a minimum of a blank line (discounting pipes (|) linking child to parent)
* The vertical pipes joining 2 left nodes should be in the column directly under the last character of the parent node (see samples)
* Column width is determined using something like `max(col_values[]).toString().length() + 2`
* Branching left always adds a new row to the tree diagram
* 2 separate (left) branches never appear on the same line (right\__right\__right is OK)
* The root node may optionally be prefixed with `__` (Removing it just about doubled my test code!)
* Input is a set of positive and/or negative integers
* You do not need to deal with duplicate values (drop/ignore them)
* I'm not placing many restrictions on trailing whitespaces:
    + You may have trailing whitespaces after the last node on a line
    + You may have trailing whitespace after a `|` on the empty lines
    + No whitespace between nodes when when branching right
* Standard loopholes and T&Cs apply
* This is . Shortest code in bytes wins!

I'm aware that this is a potential duplicate, but I think I've been specific enough in my requirements that it should pose new challenges.

## Sample Input/Output

* Input

```
(50,40,30,20,10)

```
* Output

```
__50
   |
   |__40
       |
       |__30
           |
           |__20
               |
               |__10

```
* Input

```
(10,20,30,40,50)

```
* Output

```
__10__20__30__40__50

```
* Input

```
(50,700,30,800,60,4,5,10,20,2,500,850,900,950,870,35,1,-10)

```
* Output

```
__50__700__800__850__900__950
   |    |              |
   |    |              |__870
   |    |
   |    |___60__500
   |
   |___30___35
        |
        |____4____5___10___20
             |
             |____2
                  |
                  |____1
                       |
                       |__-10

```

# Answer
> 1 votes
# Java 1286 1106 1100 bytes

Here's an easy entry to beat ;-)

Pretty messy. I traverse the tree, populating a 2d array with the node values (and left branch pipes), and a size array with the maximum column widths. Then print the node array using size array to determine correct horizontal spacing. I look forward to seeing a better way of doing this.

```
class N{N l,r;int v,i,h,g,b,e,c,j;String[][]a=new String[10][10];int[]w=new int[10];String o="",p="";N(int x){v=x;}void i(int n){if(n>v)if(r==null)r=new N(n);else r.i(n);else if(n<v)if(l==null)l=new N(n);else l.i(n);}void p(N node){a[b][h]=""+node.v;if(w[h]<a[b][h].length())w[h]=a[b][h].length();if(node.r!=null){h++;p(node.r);h--;}if(node.l!=null){b++;while(g<b)a[++g][h]="|";h++;p(node.l);if(a[--g][--h].equals("|"))g--;}}void d(){for(e=-1;++e<a.length;){o="";for(j=-1;++j<a[0].length;){p=a[e][j];if(p!=null)if(p.equals("|")){for(i=0;i++<w[j]-p.length()+2;)o+=" "; o+=p;}else for(i=0;i++<w[j]+2;)o+=" ";else for(i=0;i++<=w[j]+1;)o+=" ";}if(!o.trim().equals(""))System.out.println(o);o="";for(c=-1;++c<a[0].length;){p=a[e][c];if(p!=null)if(p.equals("|")){for(i=0;i++<w[c]-p.length()+2;)o+=" ";o+=p;}else{for(i=0;i++<w[c]-p.length()+2;)o+="_"; o+=p; }else for(i=0;i++<=w[c]+1;)o+=" ";}if(!o.trim().equals(""))System.out.println(o);}}public static void main(String[]a){String[]q=a[0].split(",");N t=new N(Integer.parseInt(q[0]));for(int i=0;i++<q.length-1;)t.i(Integer.parseInt(q[i]));t.p(t);t.d();}}

```

```
__50__700__800__850__900__950
   |    |              |
   |    |              |__870
   |    |
   |    |___60__500
   |
   |___30___35
        |
        |____4____5___10___20
             |
             |____2
                  |
                  |____1
                       |
                       |__-10

```

**Ungolfed**

```
class N {
    N leftNode, rightNode;
    int index, loop, curRight, curDown, maxDown, row,col;
    String[][] nodes = new String[10][10];
    int[] colWidths = new int[10];
    String line = "", node="";

N(int index) {
    this.index = index;
}

void i(int newValue) {
    if (newValue > index) {
        if (rightNode == null) {
            rightNode = new N(newValue);
        }
        else {
            rightNode.i(newValue);
        }
    }
    else if (newValue < index) {
        if (leftNode == null) {
            leftNode = new N(newValue);
        }
        else {
            leftNode.i(newValue);
        }
    }
}

void p(N node) {
    // Push current node
    nodes[maxDown][curRight] = ""+node.index;
    // Keep track of max column widths
    if (colWidths[curRight] < nodes[maxDown][curRight].length()) {
        colWidths[curRight] = nodes[maxDown][curRight].length();
    }
    // Branch right
    if (node.rightNode != null) {
        curRight++;
        p(node.rightNode);
        curRight--;
    }
    // Branch left
    if (node.leftNode != null) {
        maxDown++;
        while (curDown<maxDown){
            nodes[++curDown][curRight] = "|";
        }
        curRight++;
        p(node.leftNode);
        if (nodes[--curDown][--curRight].equals("|")) { //following the ladder back up
            curDown--;
        }
    }
}

void d() {
    for ( row = -1; ++row < nodes.length;) {
        // Sloppy. Inject extra rows to extend pipes (double spacing)
        line = "";
        for (int col = -1; ++col < nodes[0].length;) {
            node = nodes[row][col];
            if (node!=null){
                if (node.equals("|")) {
                    for (loop=0; loop++< colWidths[col] - node.length() + 2; ){
                        line+=" ";
                    }
                    line+=node;
                }
                else {
                    for (loop=0; loop++< colWidths[col]  + 2;){
                        line+=" ";
                    }
                }
            }
            else {
                for (loop=0; loop++<=colWidths[col]+1;){
                    line+=" ";
                }
            }
        }
        if (!line.trim().equals("")){
            System.out.println(line);
        }
        line="";

        for ( col = -1; ++col < nodes[0].length;) {
            node = nodes[row][col];
            if (node!=null){
                if (node.equals("|")) {
                    for (loop=0; loop++< colWidths[col] - node.length() + 2;){
                        line+=" ";
                    }
                    line+=node;
                }
                else {
                    for (loop=0; loop++< colWidths[col] - node.length() + 2;){
                        line+="_";
                    }
                    line+=node;
                }
            }
            else {
                for (loop=0; loop++<=colWidths[col]+1;){
                    line+=" ";
                }
            }
        }
        if (!line.trim().equals("")){
            System.out.println(line);
        }
    }
}

public static void main(String[]a){
    String[] values = a[0].split(",");
    N t=new N(Integer.parseInt(values[0]));
    for (int i=0;i++<values.length-1;)
    t.i(Integer.parseInt(values[i]));
    t.p(t);
    t.d();
}
}

```

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


# Question
Title: Fastest Longest Common Subsequence Finder
Your task is to solve the Longest Common Subsequence problem for **n** strings of length 1000.

A valid solution to the LCS problem for two or more strings **S1, … Sn** is any string **T** of maximal length such that the characters of **T** appear in all **Si**, in the same order as in **T**.

Note that **T** does not have to be a sub*string* of **Si**.

We've already solved this problem in the shortest amount of code. This time, size doesn't matter.

### Example

The strings `axbycz` and `xaybzc` have 8 common subsequences of length 3:

```
abc abz ayc ayz xbc xbz xyc xyz

```

Any of these would be a valid solution for the LCS problem.

### Details

Write a full program that solves the LCS problem, as explained above, abiding the following rules:

* The input will consist of two or more strings of length 1000, consisting of ASCII characters with code points between 0x30 and 0x3F.
* You have to read the input from STDIN.

You have two choices for the input format:

+ Each string (including the last) is followed by a linefeed.
    + The strings are chained together with no separator and no trailing linefeed.
* The number of strings will be passed as a command-line parameter to your program.
* You have to write the output, i.e., any one of the valid solutions to the LCS, to STDOUT, followed by one linefeed.
* Your language of choice has to have a free (as in beer) compiler/interpreter for my operating system (Fedora 21).
* If you require any compiler flags or a specific interpreter, please mention it in your post.

### Scoring

I will run your code with 2, 3, etc. strings until it takes longer than 120 seconds to print a valid solution. This means that you have 120 seconds for *each* value of **n**.

The highest amount of strings for which your code finished in time is your score.

In the event of a tied score of **n**, the submission that solved the problem for **n** strings in the shortest time will be declared the winner.

All submissions will be timed on *my* machine (Intel Core i7-3770, 16 GiB RAM, no swap).

The **n** strings of the **(n-1)**th test will be generated by calling `rand n` (and stripping the linefeeds, if requested), where `rand` is defined as follows:

```
rand()
{
    head -c$[500*$1] /dev/zero |
    openssl enc -aes-128-ctr -K 0 -iv $1 |
    xxd -c500 -ps |
    tr 'a-f' ':-?'
}

```

The key is `0` in the above code, but I reserve the right to change it to an undisclosed value if I suspect anybody of (partially) hardcoding the output.

# Answer
> 5 votes
# C, n = 3 in ~7 seconds

### Algorithm

The algorithm is a direct generalization of the standard dynamic programming solution to `n` sequences. For 2 strings `A` and `B`, the standard recurrence looks like this:

```
L(p, q) = 1 + L(p - 1, q - 1)           if A[p] == B[q]
        = max(L(p - 1, q), L(p, q - 1)) otherwise

```

For 3 strings `A`, `B`, `C` I use:

```
L(p, q, r) = 1 + L(p - 1, q - 1, r - 1)                          if A[p] == B[q] == C[r]
           = max(L(p - 1, q, r), L(p, q - 1, r), L(p, q, r - 1)) otherwise

```

The code implements this logic for arbitrary values of `n`.

### Efficiency

The complexity of my code is O(s ^ n), with `s` the length of the strings. Based on what I found, it looks like the problem is NP-complete. So while the posted algorithm is very inefficient for larger values of `n`, it might actually not be possible to do massively better. The only thing I saw are some approaches that improve efficiency for small alphabets. Since the alphabet is moderately small here (16), that could lead to an improvement. I still predict that nobody will find a legitimate solution that goes higher than `n = 4` in 2 minutes, and `n = 4` looks ambitious already.

I reduced the memory usage in the initial implementation, so that it could handle `n = 4` given enough time. But it only produced the length of the sequence, not the sequence itself. Check the revision history of this post for seeing that code.

### Code

Since loops over n-dimensional matrices require more logic than fixed loops, I'm using a fixed loop for the lowest dimension, and only use the generic looping logic for the remaining dimensions.

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

#define N_MAX 4

int main(int argc, char* argv[]) {
    int nSeq = argc - 1;
    if (nSeq > N_MAX) {
        nSeq = N_MAX;
    }

    char** seqA = argv + 1;

    uint64_t totLen = 1;
    uint64_t lenA[N_MAX] = {0};
    uint64_t offsA[N_MAX] = {1};
    uint64_t offsSum = 0;
    uint64_t posA[N_MAX] = {0};

    for (int iSeq = 0; iSeq < nSeq; ++iSeq) {
        lenA[iSeq] = strlen(seqA[iSeq]);
        totLen *= lenA[iSeq] + 1;

        if (iSeq + 1 < nSeq) {
            offsA[iSeq + 1] = totLen;
        }

        offsSum += offsA[iSeq];
    }

    uint16_t* mat = calloc(totLen, 2);
    uint64_t idx = offsSum;

    for (;;) {
        for (uint64_t pos0 = 0; pos0 < lenA[0]; ++pos0) {
            char firstCh = seqA[0][pos0];
            int isSame = 1;
            uint16_t maxVal = mat[idx - 1];

            for (int iSeq = 1; iSeq < nSeq; ++iSeq) {
                char ch = seqA[iSeq][posA[iSeq]];
                isSame &= (ch == firstCh);

                uint16_t val = mat[idx - offsA[iSeq]];
                if (val > maxVal) {
                    maxVal = val;
                }
            }

            if (isSame) {
                mat[idx] = mat[idx - offsSum] + 1;
            } else {
                mat[idx] = maxVal;
            }

            ++idx;
        }

        idx -= lenA[0];

        int iSeq = 1;
        while (iSeq < nSeq && posA[iSeq] == lenA[iSeq] - 1) {
            posA[iSeq] = 0;
            idx -= (lenA[iSeq] - 1) * offsA[iSeq];
            ++iSeq;
        }
        if (iSeq == nSeq) {
            break;
        }

        ++posA[iSeq];
        idx += offsA[iSeq];
    }

    int score = mat[totLen - 1];

    char* resStr = malloc(score + 1);
    resStr[score] = '\0';

    for (int iSeq = 0; iSeq < nSeq; ++iSeq) {
        posA[iSeq] = lenA[iSeq] - 1;
    }

    idx = totLen - 1;
    int resIdx = score - 1;

    while (resIdx >= 0) {
        char firstCh = seqA[0][posA[0]];
        int isSame = 1;
        uint16_t maxVal = mat[idx - 1];
        int maxIdx = 0;

        for (int iSeq = 1; iSeq < nSeq; ++iSeq) {
            char ch = seqA[iSeq][posA[iSeq]];
            isSame &= (ch == firstCh);

            uint16_t val = mat[idx - offsA[iSeq]];
            if (val > maxVal) {
                maxVal = val;
                maxIdx = iSeq;
            }
        }

        if (isSame) {
            resStr[resIdx--] = firstCh;
            for (int iSeq = 0; iSeq < nSeq; ++iSeq) {
                --posA[iSeq];
            }
            idx -= offsSum;
        } else {
            --posA[maxIdx];
            idx -= offsA[maxIdx];
        }
    }

    free(mat);

    printf("score: %d\n", score);
    printf("%s\n", resStr);

    return 0;
}

```

### Instructions for Running

To run:

* Save the code in a file, e.g. `lcs.c`.
* Compile with high optimization options. I used:

```
clang -O3 lcs.c

```

On Linux, I would try:

```
gcc -Ofast lcs.c

```
* Run with 2 to 4 sequences given as command line arguments:

```
./a.out axbycz xaybzc

```

Single quote the command line arguments if necessary, since the alphabet used for the examples contains shell special characters.

### Results

`test2.sh` and `test3.sh` are the test sequences from Dennis. I don't know the correct results, but the output looks at least plausible.

```
$ ./a.out axbycz xaybzc
score: 3
abc

$ time ./test2.sh
score: 391
16638018802020>3??3232270178;47240;24331395?<=;99=?;178675;866002==23?87?>978891>=9<6<9381992>>7030829?255>6804:=3>:;60<9384=081;0:?66=51?0;5090724<85?>>:2>7>3175?::<9199;5=0:494<5<:7100?=95<91>1887>33>67710==;48<<327::>?78>77<6:2:02:<7=5?:;>97<993;57=<<=:2=9:8=118563808=962473<::8<816<464<1==925<:5:22?>3;65=>=;27?7:5>==3=4>>5>:107:20575347>=48;<7971<<245<??219=3991=<96<??735698;62?<98928

real  0m0.012s
user  0m0.008s
sys   0m0.003s

$ time ./test3.sh
score: 269
662:2=2::=6;738395=7:=179=96662649<<;?82?=668;2?603<74:6;2=04=>6;=6>=121>1>;3=22=3=3;=3344>0;5=7>>7:75238;559133;;392<69=<778>3?593?=>9799<1>79827??6145?7<>?389?8<;;133=505>2703>02?323>;693995:=0;;;064>62<0=<97536342603>;?92034<?7:=;2?054310176?=98;5437=;13898748==<<?4

real  0m7.218s
user  0m6.701s
sys   0m0.513s

```

# Answer
> 3 votes
# This answer is currently broken due to a bug. Fixing soon...

# ~~C, 2 strings in ~35 seconds~~

This is very much a work in progress (as shown by the horrible messiness), but hopefully it sparks some good answers!

The code:

```
#include "stdlib.h"
#include "string.h"
#include "stdio.h"
#include "time.h"

/* For the versatility */
#define MIN_CODEPOINT 0x30
#define MAX_CODEPOINT 0x3F
#define NUM_CODEPOINT (MAX_CODEPOINT - MIN_CODEPOINT + 1)
#define CTOI(c) (c - MIN_CODEPOINT)

#define SIZE_ARRAY(x) (sizeof(x) / sizeof(*x))

int LCS(char** str, int num);
int getshared(char** str, int num);
int strcount(char* str, char c);

int main(int argc, char** argv) {
    char** str = NULL;
    int num = 0;
    int need_free = 0;
    if (argc > 1) {
        str = &argv[1];
        num = argc - 1;
    }
    else {
        scanf(" %d", &num);
        str = malloc(sizeof(char*) * num);
        if (!str) {
            printf("Allocation error!\n");
            return 1;
        }

        int i;
        for (i = 0; i < num; i++) {
            /* No string will exceed 1000 characters */
            str[i] = malloc(1001);
            if (!str[i]) {
                printf("Allocation error!\n");
                return 1;
            }

            scanf(" %1000s", str[i]);

            str[i][1000] = '\0';
        }

        need_free = 1;
    }

    clock_t start = clock();

    /* The call to LCS */
    int size = LCS(str, num);

    double dt = ((double)(clock() - start)) / CLOCKS_PER_SEC;
    printf("Size: %d\n", size);
    printf("Elapsed time on LCS call: %lf s\n", dt);

    if (need_free) {
        int i;
        for (i = 0; i < num; i++) {
            free(str[i]);
        }
        free(str);
    }

    return 0;
}

/* Some terribly ugly global variables... */
int depth, maximum, mapsize, lenmap[999999][2];
char* (strmap[999999][20]);
char outputstr[1000];

/* Solves the LCS problem on num strings str of lengths len */
int LCS(char** str, int num) {
    /* Counting variables */
    int i, j;

    if (depth + getshared(str, num) <= maximum) {
        return 0;
    }

    char* replace[num];
    char match;
    char best_match = 0;
    int earliest_set = 0;
    int earliest[num];
    int all_late;
    int all_early;
    int future;
    int best_future = 0;
    int need_future = 1;

    for (j = 0; j < mapsize; j++) {
        for (i = 0; i < num; i++)
            if (str[i] != strmap[j][i])
                break;
        if (i == num) {
            best_match = lenmap[j][0];
            best_future = lenmap[j][1];
            need_future = 0;
            if (best_future + depth < maximum || !best_match)
                goto J;
            else {
                match = best_match;
                goto K;
            }
        }
    }

    for (match = MIN_CODEPOINT; need_future && match <= MAX_CODEPOINT; match++) {

    K:
        future = 1;
        all_late = earliest_set;
        all_early = 1;
        for (i = 0; i < num; replace[i++]++) {
            replace[i] = strchr(str[i], match);
            if (!replace[i]) {
                future = 0;
                break;
            }

            if (all_early && earliest_set && replace[i] - str[i] > earliest[i])
                all_early = 0;
            if (all_late && replace[i] - str[i] < earliest[i])
                all_late = 0;
        }
        if (all_late) {
            future = 0;
        }

    I:
        if (future) {
            if (all_early || !earliest_set) {
                for (i = 0; i < num; i++) {
                    earliest[i] = (int)(replace[i] - str[i]);
                }
            }

            /* The recursive bit */
            depth++;
            future += LCS(replace, num);
            depth--;

            best_future = future > best_future ? (best_match = match), future : best_future;
        }
    }

    if (need_future) {
        for (i = 0; i < num; i++)
            strmap[mapsize][i] = str[i];
        lenmap[mapsize][0] = best_match;
        lenmap[mapsize++][1] = best_future;
    }

J:
    if (depth + best_future >= maximum) {
        maximum = depth + best_future;
        outputstr[depth] = best_match;
    }

    if (!depth) {
        mapsize = 0;
        maximum = 0;
        puts(outputstr);
    }

    return best_future;
}

/* Return the number of characters total (not necessarily in order) that the strings all share */
int getshared(char** str, int num) {
    int c, i, tot = 0, min;
    for (c = MIN_CODEPOINT; c <= MAX_CODEPOINT; c++) {
        min = strcount(str[0], c);
        for (i = 1; i < num; i++) {
            int count = strcount(str[i], c);
            if (count < min) {
                min = count;
            }
        }
        tot += min;
    }

    return tot;
}

/* Count the number of occurrences of c in str */
int strcount(char* str, char c) {
    int tot = 0;
    while ((str = strchr(str, c))) {
        str++, tot++;
    }
    return tot;
}

```

The relevant function that performs all of the LCS computation is the function `LCS`. The code above will time its own call to this function.

Save as `main.c` and compile with: `gcc -Ofast main.c -o FLCS`

The code can be ran either with command line arguments or through stdin. When using stdin, it expects a number of strings followed by the strings themselves.

```
~ Me$ ./FLCS "12345" "23456"
2345
Size: 4
Elapsed time on LCS call: 0.000056 s

```

Or:

```
~ Me$ ./FLCS
6
2341582491248123139182371298371239813
2348273123412983476192387461293472793
1234123948719873491234120348723412349
1234129388234888234812834881423412373
1111111112341234128469128377293477377
1234691237419274737912387476371777273
1241231212323
Size: 13
Elapsed time on LCS call: 0.001594 s

```

On a Mac OS X box with a 1.7Ghz Intel Core i7 and the test case Dennis provided, we get the following output for 2 strings:

```
16638018800200>3??32322701784=4240;24331395?<;=99=?;178675;866002==23?87?>978891>=9<66=381992>>7030829?25265804:=3>:;60<9384=081;08?66=51?0;509072488>2>924>>>3175?::<9199;330:494<51:>748571?153994<45<??20>=3991=<962508?7<2382?489
Size: 386
Elapsed time on LCS call: 33.245087 s

```

The approach is very similar to my approach to the earlier challenge, here. In addition to previous optimization, we now check for a total number of shared characters between strings at every recursion and exit early if there's no way to get a longer substring than what already exists.

For now, it handles 2 strings okay but tends to get crash-y on more. More improvements and a better explanation to come!

---
Tags: string, fastest-code, subsequence
---