Kotlin
First I must admit that about half of this is shamelessly stolen from Keith Randel's answer. I literally copied and pasted his code for finding multiplications into mine. It is very well done. I have made 2 modifications to his code.
- It is very easy to reverse the direction of any of the transitions Keith's code produces. All you have to do is replace
< with > and > with <. Ex. +[->++<]> becomes +[-<++>]<. This means that equally, good code* that only uses 2 cells can be produced.
- The second thing I did was to add a hash. To add a hash the code simply includes a
> after the .. Then for all subsequent characters, the program calculates if the code to move to the hash (such as <<<.>>>) is shorter than the regular code to produce this output. To find the locations for the hash the program loops through each character of the input and checks if hashing that character decreases the length of the program. It only hashes each type of character once which is slightly inefficient but is necessary to make the program not run like a snail.
Speaking of time complexity my program is quadratic time as opposed to Keith's which is linear. This is because the full code for any hash configuration has to be generated for each character. It is still possible to stop the algorithm early and get a better result than you started with as each cache only improves the score.
So how good does it do. Theoretically, it always does better than Keith's however, this isn't quite true. Keith's code can get to zero from any number simply by inserting a > but mine cannot because it would move too far from the hash. As a result, some of my transitions are slightly longer than Keith's meaning I actually achieve a lower score on Lenna.png. However since most of the transitions where starting with zero instead are very small or very large if you only include letters in the printable ASCII range 32 to 126 my program does beat Keith's. So although it can be worse my algorithm is better in practice. Lets look at some numbers.
Numbers
Lenna.png (no 0s), 471470 characters
Keith: 5832730 bf chars, 12.37 bf chars / input
Me: <5894582 bf chars, <12.5 bf chars / input
Keith + 0.13
Lenna.png (32 to 126), 174177 characters
Keith: 2022451 bf chars, 11.61 bf chars / input
Me: <1977716 bf chars, 11.25 bf chars / input
Me + 0.36
Hello, World!\n, 14 characters
Keith: 139 bf chars, 9.93 bf chars / input
Me: 139 bf chars, 9.93 bf chars / input
Even
I went to the store today, 25 characters
Keith: 265 bf chars, 10.6 bf chars / input
Me: 190 bf chars, 7.6 bf chars / input
Me + 3
447 characters of Lorem Ipsum
Keith: 4427 bf chars, 9.9 bf chars / input
Me: 3017 bf chars, 6.75 bf chars / input
Me + 3.15
1001 random lowercase letters
Keith: 8035 bf chars, 8.03 bf chars / input
Me: 7028 bf chars, 7.02 bf chars / input
Me + 1.01
Code
const val CELL_SIZE = 256
const val WRAPPING = true
enum class Direction {
LEFT, RIGHT;
fun opposite() = when (this) {
LEFT -> RIGHT
RIGHT -> LEFT
}
}
data class Transition(
val code: String,
val startD: Direction,
val endD: Direction,
) {
fun plus(t: Transition) = if (endD == t.startD) {
Transition(code + t.code, t.startD, t.endD)
} else {
val r = t.reverse()
Transition(code + r.code, t.startD, r.endD)
}
fun reverse(): Transition {
val newCode = code.replace(">", "|").replace("<", ">").replace("|", "<")
return Transition(newCode, startD.opposite(), endD.opposite())
}
}
var simpleTransitions = {
val list = Array(CELL_SIZE) { start ->
Array(CELL_SIZE) { end ->
var delta = end - start
if (WRAPPING) when {
delta > CELL_SIZE / 2 -> delta -= CELL_SIZE
delta < -CELL_SIZE / 2 -> delta += CELL_SIZE
}
val char = if (delta > 0) "+" else "-"
Transition(char.repeat(abs(delta)), Direction.LEFT, Direction.LEFT)
}
}
//check for multiplication
for (x in 0..255) {
for (n in 1..39) {
for (d in 1..39) {
var j = x
var y = 0
for (i in 0..255) {
if (j == 0) break
j = j - d + 256 and 255
y = y + n and 255
}
if (j == 0) {
val s = "[" + "-".repeat(d) + ">" + "+".repeat(n) + "<]>"
if (s.length < list[x][y].code.length) {
list[x][y] = Transition(s, Direction.LEFT, Direction.RIGHT)
}
}
j = x
y = 0
for (i in 0..255) {
if (j == 0) break
j = j + d and 255
y = y - n + 256 and 255
}
if (j == 0) {
val s = "[" + "+".repeat(d) + ">" + "-".repeat(n) + "<]>"
if (s.length < list[x][y].code.length) {
list[x][y] = Transition(s, Direction.LEFT, Direction.RIGHT)
}
}
}
}
}
for (i in 0 until CELL_SIZE) {
if (list[i][0].code.length > 3) list[i][0] = Transition("[-]", Direction.LEFT, Direction.LEFT)
}
var change = true
while (change) {
change = false
for (i in 0 until CELL_SIZE) {
for (j in 0 until CELL_SIZE) {
for (k in 0 until CELL_SIZE) {
if (list[i][j].code.length + list[j][k].code.length < list[i][k].code.length) {
list[i][k] = list[i][j].plus(list[j][k])
change = true
}
}
}
}
}
println("done")
list
}()
fun generate(s: String, cells: Int): String {
var caches: MutableList<Boolean> = MutableList(s.length) { false }
var currentCost = generateFromCache(s, caches)
val changes: MutableMap<Char, Int> = mutableMapOf()
if (cells > 2) {
for ((i, c) in s.withIndex()) {
val newCaches = caches.mapIndexed { index, b -> if (s[index] == c) false else b }.toMutableList()
var lowest: Char? = null
if (newCaches.count { it } >= cells - 2) {
lowest = changes.minByOrNull { it.value }!!.key
newCaches[newCaches.withIndex().indexOfFirst { it.value && s[it.index] == lowest }] = false
}
newCaches[i] = true
val newCost = generateFromCache(s, newCaches)
if (newCost.length < currentCost.length) {
println(newCost.length)
changes[c] = currentCost.length - newCost.length
currentCost = newCost
caches = newCaches
if (lowest != null) changes.remove(lowest)
}
}
}
return currentCost
}
Lenna.pngis going to dominate the score, as it is by far the largest input. Maybe normalize a bit by size? \$\endgroup\$