Code Billiards (Levenshtein golf)

Arcturus 10/16/2018 at 05:50. 4 answers, 0 views
code-golf math number multiple-holes

You must use one language to write programs that perform the following nine tasks, in any order you want.

  • Convert an inputted number from base 10 to base 36.
    • Sample input: 1000
    • Sample output: RS (output must be upper case)
  • Convert each character in a string to its base 10 decimal ASCII codes and print the codes concatenated together.
    • Sample input: Scrambled 3GG5
    • Sample output: 839911497109981081011002051717153
  • Determine if an inputted number is divisible by 1738.
    • Return a truthy value if it is and a falsy value if it isn't.
  • Determine if a string has the letter q in it.
    • Return a truthy value if it does and a falsy value if it doesn't.
  • Encode an inputted string of letters with a Caesar cipher of +1.
    • Case must be preserved. Non-letter characters will be printed without modification.
    • Sample input: Good morning, World!
    • Sample output: Hppe npsojoh, Xpsme!
  • Find and print the sum of the prime factors of a number.
    • Sample input: 1320
    • Sample output: 21
  • Print PPCG.
  • Print the first n positive integers that are divisible by floor(sqrt(n)).
    • n is an inputted integer.
  • Replace every o and O in an inputted string with .
    • Sample input: Onomatopoeia
    • Sample output: ಠnಠmatಠpಠeia

You will have noticed that this challenge is Code Billiards, not Code Golf. The objective of this challenge, like in billiards, is to set up your code so it can be modified only slightly for the next challenge. This is why your programs do not have to solve the above tasks in order.

Your score is determined as follows

  • Your score goes up by 1 each byte in your programs.
  • Your score goes up by floor(n^(1.5)) if two consecutive programs have a Levenshtein distance of n. For example if your first program is potato and your second program is taters, your score goes up by 12 for 12 bytes and by 11=floor(5^(1.5)) for a Levenshtein distance of 5.

The objective of this challenge is to have as low a score as possible after all nine programs have been written. Standard CG rules apply.


To see the leaderboard, click "Show code snippet", scroll to the bottom and click "► Run code snippet". Snippet made by Optimizer.

/* Configuration */

var QUESTION_ID = 63675; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 43444; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "http://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "http://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });  
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];
  
  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });
    
    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    else console.log(body);
  });
  
  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;
    
    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    lang = jQuery('<a>'+lang+'</a>').text();
    
    languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
    if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
body { text-align: left !important}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="language-list">
  <h2>Shortest Solution by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>

4 Answers


ETHproductions 04/13/2017.

Japt, 886 866 766 725 688 669

Tasks 5 and 6 are killers. Perhaps there are shorter ways to get them done. I think the Levenshtein distances could still be reduced as well.

  • Task 3 (divisiblity): !(U%#ۊ
    7 bytes (arabic char messes up alignment)
  • Task 4 ('q' check): U!=Uk'q 7 bytes, dist 11
  • Task 1 (base conversion): Us36 u 6 bytes, dist 14
  • Task 2 (ASCII codes): UmX=>Xc 7 bytes, dist 14
  • Task 7 (see for yourself): "PPCG" 6 bytes, dist 18
  • Task 9 (ಠ replacement): Ur"[Oo]",'ಠ 13 bytes, dist 27
  • Task 8 (floor(sqrt(n))): X=Uq f;XoU*X+1,X 16 bytes, dist 52
  • Task 6 (prime factor sum): 2oU fX=>2oX eY=>X%Y &&!(U%X)r(X,Y =>X+Y 39 bytes, dist 172
  • Task 5 (Caesar cipher): UmX=>128o mY=>Yd)a k'A i#Z,'A k'a i#z,'a gXc 44 bytes, dist 216

Here's a snippet that will tell you (one of) the most efficient ways to arrange your programs:

function L(s,t) {
  if(s == t) return 0;
  if(s.length === 0) return t.length;
  if(t.length === 0) return s.length;
  
  var v0 = Array(t.length+1),
      v1 = Array(t.length+1);
  
  for(var i=0; i<v0.length; i++) v0[i]=i;
  for(i=0; i<s.length; i++) {
    v1[0]=i+1;
    for(var j=0; j<t.length; j++)
      v1[j+1] = Math.min(v1[j]+1, v0[j+1]+1, v0[j]+(s[i]==t[j]?0:1));
    for(j=0; j<v0.length; j++) v0[j]=v1[j];
  }
  return v1[t.length];
}

function run(x) {
  R.innerHTML='';
  var b={}, k=0, min=1/0, item='';
  for(var i in x) {
    for(var j in x.slice(+i+1)) {
      k=b[i+(+i+(+j)+1)]=b[(+i+(+j)+1)+i]=L(x[+i],x[+i+(+j)+1]);
      if(k<min) min=k, item=i+(+i+(+j)+1);
    }
  }
  var order=item, q=10;
  while(order.length < x.length && q--) {
    min=1/0, item='';
    for(i in b) {
      if(b[i]<min) {
        if(i[0]==order.slice(-1) && order.indexOf(i[1])==-1)
          min = b[i], item = i[1];
      }
    }
    order+=item;
  }
  var score=0,y=0;
  function getByteCount(s){return(new Blob([s],{encoding:"UTF-8",type:"text/plain;charset=UTF-8"})).size}
  console.log("Task",(+order[0]+1)+":",y=getByteCount(x[order[0]])),score+=y
  for(i in order.slice(1))
    console.log(" ",y=Math.pow(b[order[i]+order[+i+1]],1.5)|0),score+=y,
    console.log("Task",(+order[+i+1]+1)+":",y=getByteCount(x[order[+i+1]])),score+=y;
  console.log("Total:",score)
}

console.log = function(){R.innerHTML+=Array.prototype.slice.call(arguments).join(' ');R.innerHTML+='<br>'};
<p>Input programs here, one per line:</p>
<textarea id=O rows="9" style="width:90%"></textarea><br>
<button onclick="run(O.value.split('\n'))">Run</button>
<p id=R></p>

With the latest version of Japt (non-competing in this challenge), most tasks get shorter:

  • Task 1: s36 u 5 bytes
  • Task 2: mc 2 bytes
  • Task 3: v#ۊ
    4 bytes
  • Task 4: oq 2 bytes
  • Task 5: ;B±B+C²UrF,@Bg1+BbX 19 bytes
  • Task 6: k â x 5 bytes
  • Task 7: "PPCG 5 bytes
  • Task 8: B=U¬f)oU*B+1B 13 bytes
  • Task 9: ro'ಠ'i 6 bytes

The optimal order is now 2,4,3,1,6,7,9,8,5, coming in at a whopping score of 217, less than one-third of the original!

Suggestions welcome!


Jakube 11/13/2015.

Pyth, score 489

Base conversion: 15

s@L+s`MTrG1jQ36

Caesar Cipher: 13 + 11^1.5

u.rGHrBG1z 36

Divisible by 1738: 7 + 11^1.5

!%Q1738

First N positive integers: 8 + 8^1.5

*Rs@Q2SQ

Sum of prime factors: 4 + 6^1.5

s{PQ

Appearance of q in string: 4 + 4^1.5

}\qz

Join all ASCII codes: 5 + 4^1.5

jkCMz

Print "PPCG": 5 + 5^1.5

"PPCG

Replace with : 9 + 7^1.5

Xz"oO"\ಠ

daniero 11/13/2015.

Ruby, 1488

Probably a lot of room for improvement here. Spent most of the time calculating the score...

Sum of prime factors: 64
require'prime';p gets.to_i.prime_division.reduce(0){|s,a|s+a[0]}
Base 36: 30 + 471.5 = 352
puts gets.to_i.to_s(36).upcase
Divisible by 1738: 22 + 151.5 = 80
puts gets.to_i%1738==0
Print PPCG: 9 + 181.5 = 85
puts:PPCG
Does string contain q?: 10 + 81.5 = 32
p gets[?q]
Replace o: 23 + 161.5 = 87
puts gets.gsub(/o/i,?ಠ)
Ceasar cipher: 32 + 211.5 = 128
puts gets.tr 'A-Za-z','B-ZAb-za'
ASCII codes: 37 + 261.5 = 169
puts gets.chomp.chars.map(&:ord).join
Integers divisible by square root: 72 + 561.5 = 491
puts *(1..1/0.0).lazy.select{|i|i%Math.sqrt(i).floor==0}.take(gets.to_i)

SuperJedi224 03/02/2016.

Java, score 8331

Them levenshtein distances are killing my score here.

(These programs take input as command line arguments)

Program 1 (119):

class L{public static void main(String[]a){System.out.print(Integer.toString(Integer.parseInt(a[0]),36).toUpperCase());}}

Program 2 (120+561.5=539):

class L{public static void main(String[]a){/*System.out.print*/for(char b:a[0].toCharArray())System.out.print((int)b);}}

Program 3 (101+491.5=444):

class L{public static void main(String[]a){System.out.print/*for*/(Integer.parseInt(a[0])%1738==0);}}

Program 4 (108+201.5=197):

class L{public static void main(String[]a){System.out.print(/*forInteger.parseInt(*/a[0].indexOf('q')>=0);}}

Program 5 (186+1071.5=1293):

class L{public static void main(String[]a){for(char b:a[0].toCharArray())System.out.print(Character.isLetter(b)?Character.isUpperCase(b)?b>'Y'?'A':(char)(b+1):b>'y'?'a':(char)(b+1):b);}}

Program 6 (327+2281.5=3747):

class L{public static void main(String[]a){int i,k=0,j=i=Integer.parseInt(a[0]);for(;i>0;i--)if(p(i)&&j%i==0)k+=i;System.out.print(k);}static boolean p(int n){if(n<2)return 0>0;if(n==2||n==3)return 1>0;if(n%2==0||n%3==0)return 0>0;int i,k=(int)Math.sqrt(n)+1;for(i=6;i<=k;i+=6)if(n%(i-1)==0||n%(i+1)==0)return 0>0;return 1>0;}}

Program 7 (336+101.5=368)

class L{public static void main(String[]a){/*int i,k=0,j=i=Integer.parseInt(a[0]);for(;i>0;i--)if(p(i)&&j%i==0)k+=i;*/System.out.print("PPCG");}static boolean p(int n){if(n<2)return 0>0;if(n==2||n==3)return 1>0;if(n%2==0||n%3==0)return 0>0;int i,k=(int)Math.sqrt(n)+1;for(i=6;i<=k;i+=6)if(n%(i-1)==0||n%(i+1)==0)return 0>0;return 1>0;}}

Program 8 (351+341.5=549):

class L{public static void main(String[]a){int i,k=1,j=(int)Math.sqrt(i=Integer.parseInt(a[0]));for(;k<i;k++)/*if(p(i)&&j%i==0)k+=i;*/System.out.println(j*k);}static boolean p(int n){if(n<2)return 0>0;if(n==2||n==3)return 1>0;if(n%2==0||n%3==0)return 0>0;int i,k=(int)Math.sqrt(n)+1;for(i=6;i<=k;i+=6)if(n%(i-1)==0||n%(i+1)==0)return 0>0;return 1>0;}}

Program 9 (305+841.5=1075):

class L{public static void main(String[]a){int i,k=1,j=0;System.out.print(a[0].replaceAll("o|O",""+(char)3232));}static boolean p(int n){if(n<2)return 0>0;if(n==2||n==3)return 1>0;if(n%2==0||n%3==0)return 0>0;int i,k=(int)Math.sqrt(n)+1;for(i=6;i<=k;i+=6)if(n%(i-1)==0||n%(i+1)==0)return 0>0;return 1>0;}}

HighResolutionMusic.com - Download Hi-Res Songs

1 Martin Garrix

Yottabyte flac

Martin Garrix. 2018. Writer: Martin Garrix.
2 Alan Walker

Diamond Heart flac

Alan Walker. 2018. Writer: Alan Walker;Sophia Somajo;Mood Melodies;James Njie;Thomas Troelsen;Kristoffer Haugan;Edvard Normann;Anders Froen;Gunnar Greve;Yann Bargain;Victor Verpillat;Fredrik Borch Olsen.
3 Sia

I'm Still Here flac

Sia. 2018. Writer: Sia.
4 Blinders

Breach (Walk Alone) flac

Blinders. 2018. Writer: Dewain Whitmore;Ilsey Juber;Blinders;Martin Garrix.
5 Dyro

Latency flac

Dyro. 2018. Writer: Martin Garrix;Dyro.
6 Cardi B

Taki Taki flac

Cardi B. 2018. Writer: Bava;Juan Vasquez;Vicente Saavedra;Jordan Thorpe;DJ Snake;Ozuna;Cardi B;Selena Gomez.
7 Bradley Cooper

Shallow flac

Bradley Cooper. 2018. Writer: Andrew Wyatt;Anthony Rossomando;Mark Ronson;Lady Gaga.
8 Halsey

Without Me flac

Halsey. 2018. Writer: Halsey;Delacey;Louis Bell;Amy Allen;Justin Timberlake;Timbaland;Scott Storch.
9 Lady Gaga

I'll Never Love Again flac

Lady Gaga. 2018. Writer: Benjamin Rice;Lady Gaga.
10 Kelsea Ballerini

This Feeling flac

Kelsea Ballerini. 2018. Writer: Andrew Taggart;Alex Pall;Emily Warren.
11 Mako

Rise flac

Mako. 2018. Writer: Riot Music Team;Mako;Justin Tranter.
12 Dewain Whitmore

Burn Out flac

Dewain Whitmore. 2018. Writer: Dewain Whitmore;Ilsey Juber;Emilio Behr;Martijn Garritsen.
13 Bradley Cooper

Always Remember Us This Way flac

Bradley Cooper. 2018. Writer: Lady Gaga;Dave Cobb.
14 Little Mix

Woman Like Me flac

Little Mix. 2018. Writer: Nicki Minaj;Steve Mac;Ed Sheeran;Jess Glynne.
15 Charli XCX

1999 flac

Charli XCX. 2018. Writer: Charli XCX;Troye Sivan;Leland;Oscar Holter;Noonie Bao.
16 Rita Ora

Let You Love Me flac

Rita Ora. 2018. Writer: Rita Ora.
17 Diplo

Electricity flac

Diplo. 2018. Writer: Diplo;Mark Ronson;Picard Brothers;Wynter Gordon;Romy Madley Croft;Florence Welch.
18 Jonas Blue

Polaroid flac

Jonas Blue. 2018. Writer: Jonas Blue;Liam Payne;Lennon Stella.
19 Lady Gaga

Look What I Found flac

Lady Gaga. 2018. Writer: DJ White Shadow;Nick Monson;Mark Nilan Jr;Lady Gaga.
20 Avril Lavigne

Head Above Water flac

Avril Lavigne. 2018. Writer: Stephan Moccio;Travis Clark;Avril Lavigne.

Language

Popular Tags