Submissions for TLE 2015

42.c

C(a,c,d){asm("syscall"::"a"(a/3),"D"(a%3),"S"(c),"d"(d));}char b[],*p=b;_start(){for(C(0,b,999);;)C(*(int*)(p-2)-'\n42\n'?5:180,p++,1);}

aa.c

#include<stdio.h>
unsigned char d[]="<DATA>",*p=d;
int x,c,n;
main(){
  for(;n=*p++;){
    n=n==254?800-x:n>254?*p++*256+*p++:n;
    for(;n--;x++)putchar(c?35:46);
    c=x>799?putchar(10),x=0:!c;
  }
}

aa.rb

#!/usr/bin/env ruby

require '../huffman'

aa = File.read('felicity_ascii_art.txt')

#p !!(aa =~ /^#/)

# 800x300
#p aa.split.size
#p aa.split.map{|l|l.size}.uniq

sa = []

o = ''
aa.scan(/(.)\1*/) do
  n = $&.size
  sa << ($'[0] == "\n" ? -1 : n)
  #if n == 800
  if $'[0] == "\n"
    n = 254
  end

  if n > 254
    o += 255.chr
    o += (n / 256).chr
    o += (n % 256).chr
  else
    o += n.chr
  end
end

m = Hash.new(0)
sa.each do |_|
  m[_] += 1
end
sz = 0
huffman(m).each{|char, num, code|
  sz += num * code.size
}
STDERR.puts "estimated size by huffman=#{sz/8}"

sz = 0
sa.each do |_|
  sz += if _ < 64
          5
        elsif _ < 256
          16
        else
          24
        end
end
STDERR.puts "estimated data size=#{sz/8}"

sz = 0
sa.each do |_|
  sz += if _ < 255
          1
        else
          3
        end
end
STDERR.puts "estimated data size=#{sz}"

huffman(m).each{|char, num, code|
  STDERR.puts "#{char} #{num} #{code}"
}

#p sa.sort.size
#p sa.reject{|_|_>127}.size

o.gsub!('\\', '\&\&')
o.gsub!("\"", '\\"')
o.gsub!("\n", '\\n')
o.gsub!("\r", '\\r')

system("#{ENV['HOME']}/wrk/caddy/caddy.rb -sq aa.c")
code = File.read('out.c')

code.sub!('<DATA>'){o}
File.open('out.c', 'w'){|ofile|ofile.print(code)}
r = `gcc out.c 2>&1`
if !$?.success?
  puts r
  exit 0
end

r = `./a.out`
if r == File.read('felicity_ascii_art.txt')
  puts 'OK'
else
  puts r
  puts 'FAIL'
end

puts File.size('out.c')

#p sa.sort
#p sa.sort.uniq
#p sa.size
#p sa.sort.uniq.size

distinct.cc

#include<stdio.h>
#include<string.h>
#include<map>
#include<string>
#include<iostream>
using namespace std;
int main(){
  int t,l;
  scanf("%d",&t);
  for(;t--;){
    string s;
    cin>>s;
    l=s.size();
    map<string,int> m;
    for(int i=0;i<l;i++)
      for(int j=1;j<=l-i;j++)
        m[s.substr(i,j)]=1;
    printf("%d\n",m.size());
  }
}

distinct.rb

#!/usr/bin/env ruby

system("g++ distinct.cc")
system("#{ENV['HOME']}/wrk/caddy/caddy.rb -l distinct.cc")

code = File.read('out.cc')

code += '//'
9999.times{
  code += (rand(94)+33).chr
}

File.open('out.cc', 'w') do |ofile|
  ofile.print(code)
end
exit

s = code.gsub(/\s/, '')

pipe = IO.popen('./a.out', 'r+')
pipe.puts 1
pipe.puts s

k = pipe.read.to_f
l = s.size

puts "k=#{k} l=#{l}"
puts k / l / l

gcd.cc

// 260

#include<math.h>
#include<iostream>

#define A __sync_fetch_and_add
using namespace std;

char P[9999];
int main() {
  int m,n,i;

  for(cin>>P;cin>>P;){
    for(m=i=0;P[i];)
      m=m<<1|m<<3,
        A(&m,P[A(&i,1)]^48);
    cin>>P>>n;

    m&=~(~0<<n);
    n=1<<n;

    for(;n;m=i)
      n=fmod(m,i=n);

    cout<<m<<"\n";
  }
}

halt.cc

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

#include <iostream>
#include <string>
#include <vector>

#define LOG(fmt, ...) printf(fmt, __VA_ARGS__)

using namespace std;

void error(string msg) {
  LOG("%s\n", msg.c_str());
  abort();
}

bool has(const string& p, const string& s) {
  return p.find(s) != string::npos;
}

int is_halt(const string& p) {
  if (p.find("for") == string::npos &&
      p.find("while") == string::npos)
    return 1;

  if (has(p, "main(){while(1)") && !has(p, "break"))
    return 0;

  if (has(p, "for(;;)"))
    return 0;

  return 2;
}

class CInt {
 public:
  explicit CInt(string prog)
    : prog_(prog), pc_(0) {
    steps_ = 0;
  }

  void skipws() {
    while (isspace(prog_[pc_])) {
      pc_++;
    }
  }

  char chr() {
    return prog_[pc_];
  }

  string tok() {
    skipws();

    int pc = pc_;

    string r;
    char c = chr();
    if (isalpha(c)) {
      while (isalpha(chr())) {
        r += chr();
        pc_++;
      }
    } else if (isdigit(chr())) {
      while (isdigit(chr())) {
        r += chr();
        pc_++;
      }
    } else if (c == ',' || c == ';') {
      r += c;
      pc_++;
    } else if (c == '=') {
      r += c;
      pc_++;
      if (chr() == '=') {
        r += '=';
        pc_++;
      }
    } else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '%' ||
               c == '<' || c == '>' || c == '&' || c == '^' || c == '|') {
      r += c;
      pc_++;
      c = chr();
      while ((c == '+' || c == '-' || c == '*' || c == '/' || c == '%' ||
              c == '<' || c == '>' || c == '&' || c == '^' || c == '|' ||
              c == '=') && r[r.size()-1] != '=') {
        r += c;
        pc_++;
        c = chr();
      }
    }

    skipws();

    LOG("%d %s\n", pc, r.c_str());
    return r;
  }

  int eval_tok() {
    string t = tok();
    if (t == "i" || t == "j" || t == "k") {
      return vals_[t[0] - 'i'];
    }
    if (isdigit(t[0])) {
      return atoi(t.c_str());
    }
    error("unknown tok");
  }

  int eval_fact() {
    int v = eval_tok();
    while (true) {
      int pc = pc_;
      string t = tok();
      if (t == "*") {
        v *= eval_tok();
      } else if (t == "/") {
        v /= eval_tok();
      } else if (t == "%") {
        v %= eval_tok();
      } else {
        pc_ = pc;
        break;
      }
    }
    return v;
  }

  int eval_term() {
    int v = eval_tok();
    while (true) {
      int pc = pc_;
      string t = tok();
      if (t == "+")
        v += eval_fact();
      else if (t == "-")
        v -= eval_fact();
      else {
        pc_ = pc;
        break;
      }
    }
    return v;
  }

  int eval_shift() {
    return eval_term();
  }

  int eval_gl() {
    return eval_shift();
  }

  int eval_cmp() {
    return eval_gl();
  }

  int eval_land() {
    return eval_cmp();
  }

  int eval_lxor() {
    return eval_land();
  }

  int eval_lor() {
    return eval_lxor();
  }

  int eval_and() {
    return eval_lor();
  }

  int eval_or() {
    return eval_and();
  }

  int eval_cond() {
    // TODO
    return eval_or();
  }

  int eval_assign() {
    int pc = pc_;
    string t = tok();

    if (t == "i" || t == "j" || t == "k") {
      int* p = &vals_[t[0] - 'i'];
      string op = tok();
      if (op == "=") {
        *p = eval_assign();
        return *p;
      }

      pc_ = pc;
      return eval_cond();
    } else {
      pc_ = pc;
      return eval_cond();
    }
  }

  int eval_comma() {
    int v = eval_assign();
    while (true) {
      LOG("%s\n", "comma");
      int pc = pc_;
      string t = tok();
      if (t == ",") {
        v = eval_assign();
      } else {
        pc_ = pc;
        break;
      }
    }
    return v;
  }

  int eval() {
    return eval_comma();
  }

  bool run() {
 loop:
    steps_++;
    if (steps_ > 999999)
      return false;
    LOG("step %d\n", steps_);

    int pc = pc_;
    string t = tok();

    if (t == "return") {
      LOG("return! %d\n", eval());
      return true;
    }

    if (t == ";")
      goto loop;

    if (t == "while") {
    } else if (t == "while") {
    }

    if (t == "i" || t == "j" || t == "k" || isdigit(t[0])) {
      pc_ = pc;
      eval();
      goto loop;
    }

    if (t == "int")
      goto loop;

    // ???
    return true;
  }

 private:
  string prog_;
  int pc_;
  int vals_[3];
  int steps_;
};

int main() {
  vector<string> progs;
  string s;
  while (cin >> s) {
    if (s == "main()") {
      progs.push_back("");
    }
    if (!progs.empty()) {
      progs.back() += " ";
      progs.back() += s;
    }
  }

  for(int i = 0; i<progs.size(); i++) {
    string p = progs[i];
    size_t b = p.find('{');
    size_t e = p.rfind('}');
    progs[i] = p.substr(b + 1, (e - b) - 1);
  }

  for(int i = 0; i<progs.size(); i++) {
    string p = progs[i];
    CInt cint(p);
    cint.run();
  }

  vector<bool> answers;
  for (int i = 0; i < progs.size(); i++) {
    const string& p = progs[i];
    int a = is_halt(p);
    answers.push_back(a != 0);
  }

  //answers[0] = false;
  //answers[1] = false;
  //answers[2] = false;
  //answers[3] = false;
  //answers[4] = false;
  //answers[5] = false;
  //answers[6] = false;
  //answers[7] = false;
  //answers[8] = false;
  //answers[9] = false;
  //answers[10] = false;
  //answers[11] = false;

  for (int i = 0; i < answers.size(); i++) {
    puts(answers[i] ? "yes" : "no");
  }
}

rev_quine.c

#include<ext/rope>
#define Q(q)char*b=#q;q
Q(main(int i){for(i='i�';i--;)putchar((std::string("\n#include<ext/rope>\n#define Q(q)char*b=#q;q\nQ(")+b+")")[i%165]);})