Byte Heist is a site for code golfing. It features some vanilla golf challenges or "holes", but also a variety of "restricted source" challenges, wherein your code must print the desired output while also meeting certain criteria. I have found the restricted source challenges on this site to be some of the most fun I've had with code golf in a while.
One of these holes is the Radiation Resistant Integers challenge, which I'll be solving in JavaScript. The challenge is to provide 100 expressions, corresponding to the numbers 1-100, where eval(expr) must be equal to number. But there's a twist -- the expression must still evaluate to the same number even if any single byte is removed.
For example, if I had this expression for n = 3 (it doesn't eval to 3 but pretend it does):
123+456
Then all of these expressions must also evaluate to 3 in order for it to be a valid program for this challenge:
23+456
13+456
12+456
123456
123+56
123+46
123+45
As you can imagine, this is a pretty daunting task...
The Beginning
orthoplex, the original creator of the problem, posted the problem in the code.golf Discord (which you should definitely join!) as well as a basic solution:
-
Write the powers of two as
1 = 11&13&33 2 = 22&26&66 4 = 45&212&292 8 = 88&140&424 16 = 186&1816&852 32 = 352&357&544 64 = 864&968&1104 Then OR them together with X|+00|+Y to get any desired number.
For example, 42 can be written radiation-safely as
22&26&66|+00|+88&140&424|+00|+352&357&544
Let's break this down, using 1 as an example:
-
11&13produces 9, and9&33is 1 - Removing either of the first
1s gives1&13&33, which is also 1 - The same is true for any other digit removed, or either &
As for the X|+00|+Y combination, this has to do with the fact that & has a higher precedence than |, meaning each "AND expression", as I'll call it, is evaluated before ORing everything together.
We can't simply do X|Y, because the radiation will remove the | and produce XY, an obviously invalid expression. Using the combination above, we end up with these possibilities:
<radiated_x>|+00|+Y --> <Still a valid X>|Y --> Desired outcome
X+00|+Y --> X|Y
X|00|+Y --> X|Y
X|+0|+Y --> X|Y
X|+00+Y --> X|Y
X|+00|Y --> X|Y
X|+00|+<radiated_y> --> X|<Still a valid Y>
Using this, we can generate every number 1-100, producing the baseline 4610:
11&13&33
22&26&66
22&26&66|+00|+11&13&33
45&212&292
45&212&292|+00|+11&13&33
45&212&292|+00|+22&26&66
45&212&292|+00|+22&26&66|+00|+11&13&33
88&140&424
88&140&424|+00|+11&13&33
88&140&424|+00|+22&26&66
88&140&424|+00|+22&26&66|+00|+11&13&33
88&140&424|+00|+45&212&292
88&140&424|+00|+45&212&292|+00|+11&13&33
88&140&424|+00|+45&212&292|+00|+22&26&66
88&140&424|+00|+45&212&292|+00|+22&26&66|+00|+11&13&33
186&1816&852
186&1816&852|+00|+11&13&33
186&1816&852|+00|+22&26&66
186&1816&852|+00|+22&26&66|+00|+11&13&33
186&1816&852|+00|+45&212&292
186&1816&852|+00|+45&212&292|+00|+11&13&33
186&1816&852|+00|+45&212&292|+00|+22&26&66
186&1816&852|+00|+45&212&292|+00|+22&26&66|+00|+11&13&33
186&1816&852|+00|+88&140&424
186&1816&852|+00|+88&140&424|+00|+11&13&33
186&1816&852|+00|+88&140&424|+00|+22&26&66
186&1816&852|+00|+88&140&424|+00|+22&26&66|+00|+11&13&33
186&1816&852|+00|+88&140&424|+00|+45&212&292
186&1816&852|+00|+88&140&424|+00|+45&212&292|+00|+11&13&33
186&1816&852|+00|+88&140&424|+00|+45&212&292|+00|+22&26&66
186&1816&852|+00|+88&140&424|+00|+45&212&292|+00|+22&26&66|+00|+11&13&33
352&357&544
352&357&544|+00|+11&13&33
352&357&544|+00|+22&26&66
352&357&544|+00|+22&26&66|+00|+11&13&33
352&357&544|+00|+45&212&292
352&357&544|+00|+45&212&292|+00|+11&13&33
352&357&544|+00|+45&212&292|+00|+22&26&66
352&357&544|+00|+45&212&292|+00|+22&26&66|+00|+11&13&33
352&357&544|+00|+88&140&424
352&357&544|+00|+88&140&424|+00|+11&13&33
352&357&544|+00|+88&140&424|+00|+22&26&66
352&357&544|+00|+88&140&424|+00|+22&26&66|+00|+11&13&33
352&357&544|+00|+88&140&424|+00|+45&212&292
352&357&544|+00|+88&140&424|+00|+45&212&292|+00|+11&13&33
352&357&544|+00|+88&140&424|+00|+45&212&292|+00|+22&26&66
352&357&544|+00|+88&140&424|+00|+45&212&292|+00|+22&26&66|+00|+11&13&33
352&357&544|+00|+186&1816&852
352&357&544|+00|+186&1816&852|+00|+11&13&33
352&357&544|+00|+186&1816&852|+00|+22&26&66
352&357&544|+00|+186&1816&852|+00|+22&26&66|+00|+11&13&33
352&357&544|+00|+186&1816&852|+00|+45&212&292
352&357&544|+00|+186&1816&852|+00|+45&212&292|+00|+11&13&33
352&357&544|+00|+186&1816&852|+00|+45&212&292|+00|+22&26&66
352&357&544|+00|+186&1816&852|+00|+45&212&292|+00|+22&26&66|+00|+11&13&33
352&357&544|+00|+186&1816&852|+00|+88&140&424
352&357&544|+00|+186&1816&852|+00|+88&140&424|+00|+11&13&33
352&357&544|+00|+186&1816&852|+00|+88&140&424|+00|+22&26&66
352&357&544|+00|+186&1816&852|+00|+88&140&424|+00|+22&26&66|+00|+11&13&33
352&357&544|+00|+186&1816&852|+00|+88&140&424|+00|+45&212&292
352&357&544|+00|+186&1816&852|+00|+88&140&424|+00|+45&212&292|+00|+11&13&33
352&357&544|+00|+186&1816&852|+00|+88&140&424|+00|+45&212&292|+00|+22&26&66
352&357&544|+00|+186&1816&852|+00|+88&140&424|+00|+45&212&292|+00|+22&26&66|+00|+11&13&33
864&968&1104
864&968&1104|+00|+11&13&33
864&968&1104|+00|+22&26&66
864&968&1104|+00|+22&26&66|+00|+11&13&33
864&968&1104|+00|+45&212&292
864&968&1104|+00|+45&212&292|+00|+11&13&33
864&968&1104|+00|+45&212&292|+00|+22&26&66
864&968&1104|+00|+45&212&292|+00|+22&26&66|+00|+11&13&33
864&968&1104|+00|+88&140&424
864&968&1104|+00|+88&140&424|+00|+11&13&33
864&968&1104|+00|+88&140&424|+00|+22&26&66
864&968&1104|+00|+88&140&424|+00|+22&26&66|+00|+11&13&33
864&968&1104|+00|+88&140&424|+00|+45&212&292
864&968&1104|+00|+88&140&424|+00|+45&212&292|+00|+11&13&33
864&968&1104|+00|+88&140&424|+00|+45&212&292|+00|+22&26&66
864&968&1104|+00|+88&140&424|+00|+45&212&292|+00|+22&26&66|+00|+11&13&33
864&968&1104|+00|+186&1816&852
864&968&1104|+00|+186&1816&852|+00|+11&13&33
864&968&1104|+00|+186&1816&852|+00|+22&26&66
864&968&1104|+00|+186&1816&852|+00|+22&26&66|+00|+11&13&33
864&968&1104|+00|+186&1816&852|+00|+45&212&292
864&968&1104|+00|+186&1816&852|+00|+45&212&292|+00|+11&13&33
864&968&1104|+00|+186&1816&852|+00|+45&212&292|+00|+22&26&66
864&968&1104|+00|+186&1816&852|+00|+45&212&292|+00|+22&26&66|+00|+11&13&33
864&968&1104|+00|+186&1816&852|+00|+88&140&424
864&968&1104|+00|+186&1816&852|+00|+88&140&424|+00|+11&13&33
864&968&1104|+00|+186&1816&852|+00|+88&140&424|+00|+22&26&66
864&968&1104|+00|+186&1816&852|+00|+88&140&424|+00|+22&26&66|+00|+11&13&33
864&968&1104|+00|+186&1816&852|+00|+88&140&424|+00|+45&212&292
864&968&1104|+00|+186&1816&852|+00|+88&140&424|+00|+45&212&292|+00|+11&13&33
864&968&1104|+00|+186&1816&852|+00|+88&140&424|+00|+45&212&292|+00|+22&26&66
864&968&1104|+00|+186&1816&852|+00|+88&140&424|+00|+45&212&292|+00|+22&26&66|+00|+11&13&33
864&968&1104|+00|+352&357&544
864&968&1104|+00|+352&357&544|+00|+11&13&33
864&968&1104|+00|+352&357&544|+00|+22&26&66
864&968&1104|+00|+352&357&544|+00|+22&26&66|+00|+11&13&33
864&968&1104|+00|+352&357&544|+00|+45&212&292
But since the gold is currently sitting just above 1200, clearly we can do better.
The Early Days
The most obvious question to ask is, "Where did these AND expressions come from?" Well, we'll come back to that, since that wasn't the first thing I tried. Instead, I was looking at that expression separator -- is there something shorter to combine two expressions?
It turns out, there is! We don't need the second +, thus we can use X|+00|Y. Let's plug it in and net us a nice -219 bytes, for a 4391:
11&13&33
22&26&66
22&26&66|+00|11&13&33
45&212&292
45&212&292|+00|11&13&33
45&212&292|+00|22&26&66
45&212&292|+00|22&26&66|+00|11&13&33
88&140&424
88&140&424|+00|11&13&33
88&140&424|+00|22&26&66
88&140&424|+00|22&26&66|+00|11&13&33
88&140&424|+00|45&212&292
88&140&424|+00|45&212&292|+00|11&13&33
88&140&424|+00|45&212&292|+00|22&26&66
88&140&424|+00|45&212&292|+00|22&26&66|+00|11&13&33
186&1816&852
186&1816&852|+00|11&13&33
186&1816&852|+00|22&26&66
186&1816&852|+00|22&26&66|+00|11&13&33
186&1816&852|+00|45&212&292
186&1816&852|+00|45&212&292|+00|11&13&33
186&1816&852|+00|45&212&292|+00|22&26&66
186&1816&852|+00|45&212&292|+00|22&26&66|+00|11&13&33
186&1816&852|+00|88&140&424
186&1816&852|+00|88&140&424|+00|11&13&33
186&1816&852|+00|88&140&424|+00|22&26&66
186&1816&852|+00|88&140&424|+00|22&26&66|+00|11&13&33
186&1816&852|+00|88&140&424|+00|45&212&292
186&1816&852|+00|88&140&424|+00|45&212&292|+00|11&13&33
186&1816&852|+00|88&140&424|+00|45&212&292|+00|22&26&66
186&1816&852|+00|88&140&424|+00|45&212&292|+00|22&26&66|+00|11&13&33
352&357&544
352&357&544|+00|11&13&33
352&357&544|+00|22&26&66
352&357&544|+00|22&26&66|+00|11&13&33
352&357&544|+00|45&212&292
352&357&544|+00|45&212&292|+00|11&13&33
352&357&544|+00|45&212&292|+00|22&26&66
352&357&544|+00|45&212&292|+00|22&26&66|+00|11&13&33
352&357&544|+00|88&140&424
352&357&544|+00|88&140&424|+00|11&13&33
352&357&544|+00|88&140&424|+00|22&26&66
352&357&544|+00|88&140&424|+00|22&26&66|+00|11&13&33
352&357&544|+00|88&140&424|+00|45&212&292
352&357&544|+00|88&140&424|+00|45&212&292|+00|11&13&33
352&357&544|+00|88&140&424|+00|45&212&292|+00|22&26&66
352&357&544|+00|88&140&424|+00|45&212&292|+00|22&26&66|+00|11&13&33
352&357&544|+00|186&1816&852
352&357&544|+00|186&1816&852|+00|11&13&33
352&357&544|+00|186&1816&852|+00|22&26&66
352&357&544|+00|186&1816&852|+00|22&26&66|+00|11&13&33
352&357&544|+00|186&1816&852|+00|45&212&292
352&357&544|+00|186&1816&852|+00|45&212&292|+00|11&13&33
352&357&544|+00|186&1816&852|+00|45&212&292|+00|22&26&66
352&357&544|+00|186&1816&852|+00|45&212&292|+00|22&26&66|+00|11&13&33
352&357&544|+00|186&1816&852|+00|88&140&424
352&357&544|+00|186&1816&852|+00|88&140&424|+00|11&13&33
352&357&544|+00|186&1816&852|+00|88&140&424|+00|22&26&66
352&357&544|+00|186&1816&852|+00|88&140&424|+00|22&26&66|+00|11&13&33
352&357&544|+00|186&1816&852|+00|88&140&424|+00|45&212&292
352&357&544|+00|186&1816&852|+00|88&140&424|+00|45&212&292|+00|11&13&33
352&357&544|+00|186&1816&852|+00|88&140&424|+00|45&212&292|+00|22&26&66
352&357&544|+00|186&1816&852|+00|88&140&424|+00|45&212&292|+00|22&26&66|+00|11&13&33
864&968&1104
864&968&1104|+00|11&13&33
864&968&1104|+00|22&26&66
864&968&1104|+00|22&26&66|+00|11&13&33
864&968&1104|+00|45&212&292
864&968&1104|+00|45&212&292|+00|11&13&33
864&968&1104|+00|45&212&292|+00|22&26&66
864&968&1104|+00|45&212&292|+00|22&26&66|+00|11&13&33
864&968&1104|+00|88&140&424
864&968&1104|+00|88&140&424|+00|11&13&33
864&968&1104|+00|88&140&424|+00|22&26&66
864&968&1104|+00|88&140&424|+00|22&26&66|+00|11&13&33
864&968&1104|+00|88&140&424|+00|45&212&292
864&968&1104|+00|88&140&424|+00|45&212&292|+00|11&13&33
864&968&1104|+00|88&140&424|+00|45&212&292|+00|22&26&66
864&968&1104|+00|88&140&424|+00|45&212&292|+00|22&26&66|+00|11&13&33
864&968&1104|+00|186&1816&852
864&968&1104|+00|186&1816&852|+00|11&13&33
864&968&1104|+00|186&1816&852|+00|22&26&66
864&968&1104|+00|186&1816&852|+00|22&26&66|+00|11&13&33
864&968&1104|+00|186&1816&852|+00|45&212&292
864&968&1104|+00|186&1816&852|+00|45&212&292|+00|11&13&33
864&968&1104|+00|186&1816&852|+00|45&212&292|+00|22&26&66
864&968&1104|+00|186&1816&852|+00|45&212&292|+00|22&26&66|+00|11&13&33
864&968&1104|+00|186&1816&852|+00|88&140&424
864&968&1104|+00|186&1816&852|+00|88&140&424|+00|11&13&33
864&968&1104|+00|186&1816&852|+00|88&140&424|+00|22&26&66
864&968&1104|+00|186&1816&852|+00|88&140&424|+00|22&26&66|+00|11&13&33
864&968&1104|+00|186&1816&852|+00|88&140&424|+00|45&212&292
864&968&1104|+00|186&1816&852|+00|88&140&424|+00|45&212&292|+00|11&13&33
864&968&1104|+00|186&1816&852|+00|88&140&424|+00|45&212&292|+00|22&26&66
864&968&1104|+00|186&1816&852|+00|88&140&424|+00|45&212&292|+00|22&26&66|+00|11&13&33
864&968&1104|+00|352&357&544
864&968&1104|+00|352&357&544|+00|11&13&33
864&968&1104|+00|352&357&544|+00|22&26&66
864&968&1104|+00|352&357&544|+00|22&26&66|+00|11&13&33
864&968&1104|+00|352&357&544|+00|45&212&292
Now, obviously a very rational person would next try a Magical Substring Remover to see if we can simply chop off parts of expressions. Critically thinking about a smarter way to do it? Analyzing why this sometimes works or what it's really doing? Pssh, that's for noobs.
In the interest of brevity, I won't post the full 100 expressions for every save I have written down. I also won't share the truly awful code I used for the substring removal, since it is very inefficient and may or may not be tactfully inspired by sources on the internet, but it did bring us down 116 bytes to a 4275. Here's one expression that got reduced:
// 11 before
88&140&424|+00|22&26&66|+00|11&13&33
// 11 after
88&140&424|+00|22&26&66|+00|11
As you can see, it removed part of the end, because it wasn't really needed for this particular case. My remover only checked lobbing off beginning or ending of strings (i.e. no putting "holes" in the string), which limited its capability but kept brute force times reasonable. If you're thinking there's a much smarter way to do this -- there is, but unfortunately I got blinded by the trees and spent way too much time trying to optimize this approach.
Anyway, I decided this was a good point to investigate these AND expressions -- were these actually the best ones? It turns out, no: 4 and 16 have shorter expressions!
// 4 and 16 before
45&212&292
186&1816&852
// 4 and 16 after
77&444&54
280&592&528
Fantastic, let's plug that back into our power of 2 expression generator and- oh... it failed?
The Octal/First-Only Problem
I refer to this as the octal problem or a first-only expression (the reason why will become clear shortly). As it turns out, when we switched from X|+00|+Y to X|+00|Y, we got incredibly lucky: The + was actually doing something important, but we just so happened to not need it for these particular expressions. But as soon as we changed them, we no longer got lucky.
What's going on here is when the radiation removes the second |, we get X|+00Y. In JavaScript, numbers starting with 0 are treated as octal literals. So, what we're really doing is turning the first number in the second expression to its octal form.
If the number contains an 8 or a 9 anywhere, it gets treated as normal decimal number and so we have no issues. But if not, it's converted from octal to decimal. Sometimes, this different number just-so-happens to also satisfy the expression, but sometimes it doesn't.
Take the original expression list. 8 (88), 16 (186), and 64 (864) don't have this issue because of the 8s making it be treated as a decimal literal. But the others are turned into different numbers. For example, 1's 011&13&33 gets interpreted as 9&13&33, which luckily is still 1. This applies for every one of the original powers of 2.
Our newer 16 also is safe because it starts with 280. Our new 4, though, is not so lucky -- 077 = 63, and 63&444&54 is 52, not 4.
There's an easy fix -- just add a + at the front of the AND expression, for a cost of 1 byte. But there's another: move that AND expression to the very front of the overall expression, at no cost. This can only be used once, so we still prefer expressions that don't need a +, but it means it sometimes saves bytes, so any expression finder we use will prefer shorter expressions even if it's now a "first-only" expression compared to the longer one that isn't.
With our shiny new 4 and 16, and our horridly inefficient substring remover, we get another 142 bytes off for a total of 4133:
11&13&33
22&26&66
22&26&66|+00|11&13&33
77&444&54
77&444&54|+00|11&13&33
77&444&54|+00|22&26&66
77&444&54|+00|22&26&66|+00|11&13&33
88&140&424
88&140&424|+00|11&13&33
88&140&424|+00|22&26&66
88&140&424|+00|22&26&66|+00|11
77&444&54|+00|88&140&424
77&444&54|+00|88&140&424|+00|11&13&33
77&444&54|+00|88&140&424|+00|22&26&66
77&444&54|+00|88&140&424|+00|22&26&66|+00|11
280&592&528
280&592&528|+00|11&13&33
280&592&528|+00|22&26&66
280&592&528|+00|22&26&66|+00|11&13&33
77&444&54|+00|280&592&528
77&444&54|+00|280&592&528|+00|11&13&33
77&444&54|+00|280&592&528|+00|22
77&444&54|+00|280&592&528|+00|22&26&66|+00|11&13&33
280&592&528|+00|88&140&424
280&592&528|+00|88&140&424|+00|11&13&33
280&592&528|+00|88&140&424|+00|22&26&66
280&592&528|+00|88&140&424|+00|22&26&66|+00|11
77&444&54|+00|280&592&528|+00|88&140&424
77&444&54|+00|280&592&528|+00|88&140&424|+00|11&13&33
28|+00|88&140&424|+00|22
77&444&54|+00|280&592&528|+00|88&140&424|+00|22&26&66|+00|11
352&357&544
352&357&544|+00|11&13&33
352&357&544|+00|22&26&66
352&357&544|+00|22&26&66|+00|11&13&33
77&444&54|+00|352&357&544
77&444&54|+00|352&357&544|+00|11&13&33
77&444&54|+00|352&357&544|+00|22&26&66
77&444&54|+00|352&357&544|+00|22&26&66|+00|11&13&33
352&357&544|+00|88&140&424
352&357&544|+00|88&140&424|+00|11&13&33
352&357&544|+00|88&140&424|+00|22&26&66
352&357&544|+00|88&140&424|+00|22&26&66|+00|11
77&444&54|+00|352&357&544|+00|88&140&424
77&444&54|+00|352&357&544|+00|88&140&424|+00|11&13&33
77&444&54|+00|352&357&544|+00|88&140&424|+00|22&26&66
77&444&54|+00|352&357&544|+00|88&140&424|+00|22&26&66|+00|11
352&357&544|+00|280&592&528
352&357&544|+00|280&592&528|+00|11&13&33
352&357&544|+00|280&592&528|+00|22&26&66
352&357&544|+00|280&592&528|+00|22&26&66|+00|11&13&33
77&444&54|+00|352&357&544|+00|280&592&528
77&444&54|+00|352&357&544|+00|280&592&528|+00|11&13&33
77&444&54|+00|352&357&544|+00|280&592&528|+00|22
54|+00|352&357&544|+00|280&592&528|+00|22&26&66|+00|11&13&33
352&357&544|+00|280&592&528|+00|88&140&424
352&357&544|+00|280&592&528|+00|88&140&424|+00|11&13&33
352&357&544|+00|280&592&528|+00|88&140&424|+00|22&26&66
352&357&544|+00|280&592&528|+00|88&140&424|+00|22&26&66|+00|11
77&444&54|+00|352&357&544|+00|280&592&528|+00|88&140&424
77&444&54|+00|352&357&544|+00|280&592&528|+00|88&140&424|+00|11&13&33
77&444&54|+00|352&357&544|+00|280&592&528|+00|88&140&424|+00|22
54|+00|352&357&544|+00|280&592&528|+00|88&140&424|+00|22&26&66|+00|11
864&968&1104
864&968&1104|+00|11&13&33
864&968&1104|+00|22&26&66
864&968&1104|+00|22&26&66|+00|11&13&33
77&444&54|+00|864&968&1104
77&444&54|+00|864&968&1104|+00|11&13&33
77&444&54|+00|864&968&1104|+00|22&26&66
77&444&54|+00|864&968&1104|+00|22&26&66|+00|11&13&33
864&968&1104|+00|88&140&424
864&968&1104|+00|88&140&424|+00|11&13&33
864&968&1104|+00|88&140&424|+00|22&26&66
864&968&1104|+00|88&140&424|+00|22&26&66|+00|11
77&444&54|+00|864&968&1104|+00|88&140&424
77&444&54|+00|864&968&1104|+00|88&140&424|+00|11&13&33
77&444&54|+00|864&968&1104|+00|88&140&424|+00|22&26&66
77&444&54|+00|864&968&1104|+00|88&140&424|+00|22&26&66|+00|11
864&968&1104|+00|280&592&528
864&968&1104|+00|280&592&528|+00|11&13&33
864&968&1104|+00|280&592&528|+00|22&26&66
864&968&1104|+00|280&592&528|+00|22&26&66|+00|11&13&33
77&444&54|+00|864&968&1104|+00|280&592&528
77&444&54|+00|864&968&1104|+00|280&592&528|+00|11&13&33
77&444&54|+00|864&968&1104|+00|280&592&528|+00|22
77&444&54|+00|864&968&1104|+00|280&592&528|+00|22&26&66|+00|11&13&33
864&968&1104|+00|280&592&528|+00|88
864&968&1104|+00|280&592&528|+00|88&140&424|+00|11&13&33
864&968&1104|+00|280&592&528|+00|88&140&424|+00|22&26&66
864&968&1104|+00|280&592&528|+00|88&140&424|+00|22&26&66|+00|11
77&444&54|+00|864&968&1104|+00|280&592&528|+00|88
77&444&54|+00|864&968&1104|+00|280&592&528|+00|88&140&424|+00|11&13&33
77&444&54|+00|864&968&1104|+00|280&592&528|+00|88&140&424|+00|22
77&444&54|+00|864&968&1104|+00|280&592&528|+00|88&140&424|+00|22&26&66|+00|11
864&968&1104|+00|352&357&544
864&968&1104|+00|352&357&544|+00|11&13&33
864&968&1104|+00|352&357&544|+00|22&26&66
864&968&1104|+00|352&357&544|+00|22&26&66|+00|11&13&33
77&444&54|+00|864&968&1104|+00|352&357&544
MORE AND MORE AND MORE
Our next frontier is analyzing another assumption -- why are we using powers of 2? Surely, we can just run the AND expression finder on every number, right?
Well, yes! ...Kind of. We'll quickly discover why the powers of 2 were chosen in the first place -- they were all findable very quickly, and also makes for a simple generator program for the related hole.
Indeed, checking up to 2,000 took about 8 hours on my machine, but it produced these numbers:
const known = { // n: [expr, firstOnly?]
1: ["11&13&33", false],
2: ["22&26&66", false],
3: ["115&715&151", true],
4: ["77&444&54", true],
8: ["88&140&424", false],
16: ["280&592&528", false],
32: ["352&357&544", false],
34: ["354&554&550", true],
35: ["355&555&555", true],
64: ["864&968&1104", false],
65: ["1097&977&1093", false],
66: ["1110&866&1226", true],
};
There's actually one more problem we introduce when we don't stick to strictly powers of 2 -- there are multiple ways to get to a solution.
Take for example the number 11. We can get to it by 8|2|1, or we can use 8|3. Which one is better? For our currently very small expressions, 8|3 is going to take the cake. But what about a more complex number like 51? 35|32|16 and 32|16|3 both work. How do we know which one is better? Simple: We check them all and pick the shortest.
Using just these expressions alone plus a simple combination checker, we shave a whopping 607 bytes to get us to 3526!
11&13&33
22&26&66
115&715&151
77&444&54
77&444&54|+00|11&13&33
77&444&54|+00|22&26&66
115&715&151|+00|+77&444&54
88&140&424
11&13&33|+00|88&140&424
22&26&66|+00|88&140&424
115&715&151|+00|88&140&424
77&444&54|+00|88&140&424
77&444&54|+00|11&13&33|+00|88&140&424
77&444&54|+00|22&26&66|+00|88&140&424
115&715&151|+00|+77&444&54|+00|88&140&424
280&592&528
11&13&33|+00|280&592&528
22&26&66|+00|280&592&528
115&715&151|+00|280&592&528
77&444&54|+00|280&592&528
77&444&54|+00|11&13&33|+00|280&592&528
77&444&54|+00|22&26&66|+00|280&592&528
115&715&151|+00|+77&444&54|+00|280&592&528
88&140&424|+00|280&592&528
11&13&33|+00|88&140&424|+00|280&592&528
22&26&66|+00|88&140&424|+00|280&592&528
115&715&151|+00|88&140&424|+00|280&592&528
77&444&54|+00|88&140&424|+00|280&592&528
77&444&54|+00|11&13&33|+00|88&140&424|+00|280&592&528
77&444&54|+00|22&26&66|+00|88&140&424|+00|280&592&528
115&715&151|+00|+77&444&54|+00|88&140&424|+00|280&592&528
352&357&544
11&13&33|+00|352&357&544
354&554&550
355&555&555
77&444&54|+00|352&357&544
77&444&54|+00|11&13&33|+00|352&357&544
77&444&54|+00|+354&554&550
77&444&54|+00|+355&555&555
88&140&424|+00|352&357&544
11&13&33|+00|88&140&424|+00|352&357&544
354&554&550|+00|88&140&424
355&555&555|+00|88&140&424
77&444&54|+00|88&140&424|+00|352&357&544
77&444&54|+00|11&13&33|+00|88&140&424|+00|352&357&544
77&444&54|+00|88&140&424|+00|+354&554&550
77&444&54|+00|88&140&424|+00|+355&555&555
280&592&528|+00|352&357&544
11&13&33|+00|280&592&528|+00|352&357&544
354&554&550|+00|280&592&528
355&555&555|+00|280&592&528
77&444&54|+00|280&592&528|+00|352&357&544
77&444&54|+00|11&13&33|+00|280&592&528|+00|352&357&544
77&444&54|+00|280&592&528|+00|+354&554&550
54|+00|280&592&528|+00|+35
88&140&424|+00|280&592&528|+00|352&357&544
11&13&33|+00|88&140&424|+00|280&592&528|+00|352&357&544
354&554&550|+00|88&140&424|+00|280&592&528
355&555&555|+00|88&140&424|+00|280&592&528
77&444&54|+00|88&140&424|+00|280&592&528|+00|352&357&544
77&444&54|+00|11&13&33|+00|88&140&424|+00|280&592&528|+00|352&357&544
77&444&54|+00|88&140&424|+00|280&592&528|+00|+354&554&550
54|+00|88&140&424|+00|280&592&528|+00|35
864&968&1104
1097&977&1093
1110&866&1226
22&26&66|+00|1097&977&1093
77&444&54|+00|864&968&1104
77&444&54|+00|1097&977&1093
77&444&54|+00|+1110&866&1226
66|+00|+77&444&54|+00|1097&977&1093
88&140&424|+00|864&968&1104
88&140&424|+00|1097&977&1093
1110&866&1226|+00|88&140&424
22&26&66|+00|88&140&424|+00|1097&977&1093
77&444&54|+00|88&140&424|+00|864&968&1104
77&444&54|+00|88&140&424|+00|1097&977&1093
77&444&54|+00|88&140&424|+00|+1110&866&1226
66|+00|+77&444&54|+00|88&140&424|+00|1097&977&1093
280&592&528|+00|864&968&1104
280&592&528|+00|1097&977&1093
1110&866&1226|+00|280&592&528
22&26&66|+00|280&592&528|+00|1097&977&1093
77&444&54|+00|280&592&528|+00|864&968&1104
77&444&54|+00|280&592&528|+00|1097&977&1093
77&444&54|+00|280&592&528|+00|+1110&866&1226
66|+00|+77&444&54|+00|280&592&528|+00|1097&977&1093
88&140&424|+00|280&592&528|+00|864&968&1104
88&140&424|+00|280&592&528|+00|1097&977&1093
1110&866&1226|+00|88&140&424|+00|280&592&528
22&26&66|+00|88&140&424|+00|280&592&528|+00|1097&977&1093
77&444&54|+00|88&140&424|+00|280&592&528|+00|864&968&1104
77&444&54|+00|88&140&424|+00|280&592&528|+00|1097&977&1093
77&444&54|+00|88&140&424|+00|280&592&528|+00|+1110&866&1226
66|+00|+77&444&54|+00|88&140&424|+00|280&592&528|+00|1097&977&1093
352&357&544|+00|864&968&1104
352&357&544|+00|1097&977&1093
354&554&550|+00|864&968&1104
355&555&555|+00|864&968&1104
77&444&54|+00|352&357&544|+00|864&968&1104
Better Bruteforcing Bureau
One of the central themes going forward is better bruteforcing. Testing even just up to 10,000 each of a, b, and c would require testing 1e12 expressions, or 1 trillion. And remember each expression has to have several calculations ran on it to check for radiation safety. Clearly, a naïve bruteforce isn't going to cut it.
One of the easiest but most powerful optimizations we can do is realize that expressions of the form a&b&c only remove bits, not add them. So if we have a factor a and it has a "missing" bit from the final output, we don't bother checking any as (or bs or cs) using that number since it's a waste of time -- it will never get us to our desired answer.
For example, the number 1 in binary is... 1. Thus, we know we cannot possibly use the factor 2 since its binary is 10, which is missing a bit that cannot be added back. For 1 specifically, this automatically removes all even numbers from the running.
This optimization works best for numbers with many bits set, since this will greatly prune the factor candidate list.
Another optimization is realizing when a candidate expression is too long to save any bytes, based on our currently-best 100 expression list. This lets us shortcut longer factors, especially when we know the final expression should be short. For example, if we have 12345&67890, which is 11 bytes, and we know c has a minimum size of 3 (say the minimum factor that passes the above optimization is 777), then the minimum expression size for this "a&b branch" is 15 bytes (don't forget +1 for the 2nd &). If we already have an expression that is 14 bytes, then we can simply skip this a&b branch and not bother checking the cs since we know it won't be shorter.
At this stage of my journey, the above optimizations were pretty primitive (and sloppily written), which is why I'm not sharing my generating code for this. I promise the final versions will be posted later, letting you see all these optimizations in their full glory!
A New Chapter
With these optimizations in play, we get a massively expanded list of AND expressions. I also took this time to completely rewrite my "expression combinator", the piece of code that brute force checked every OR-combination to see which set of AND expressions produced the best result. The main change? I finally got rid of the horrible substring and permutation bruteforcer, and instead only did various substring checks on individual factors. (Permutation bruteforcer? Yeah, I won't get into it, but remember how my substring reducer only removed beginning and ends of strings? Well my 4000 IQ galaxy brain thought it would be smart to simply permute or shuffle each AND expression combination then run it through the substring function. This did technically work, but it was so horrifically slow it almost made me lose interest in this problem. But my new and improved combinator function checked every factor individually, removing the need for any permuting!)
These improvements -- only speeding up bruteforcing, no change in strategy -- nearly halved our byte count, all the way down to the lovely 2023!
const known = { // n: [expr, firstOnly?] // 40 numbers
1: ["11&13&33", false],
2: ["22&26&66", false],
3: ["195&595&515", false],
4: ["77&444&54", true],
5: ["77&855&18213", false],
6: ["223&3110&1190", true],
7: ["3119&39111&9111", false],
8: ["88&140&424", false],
9: ["111&4777&8457", false],
10: ["462&6666&794", true],
11: ["111&6555&8795", true],
12: ["6222&71500&444", true],
14: ["82222&6223&331998", false],
16: ["280&592&528", false],
17: ["3379&217&817", false],
18: ["222&4114&4114", false],
19: ["65559&955&65555", false],
20: ["8221&88855&220", false],
21: ["199991&133333&533333", false],
24: ["888&999992&44440", false],
28: ["4477&551966&844444", false],
32: ["352&357&544", false],
33: ["353&3173&553", false],
34: ["354&554&550", true],
35: ["355&555&555", true],
36: ["444&3108&8228", false],
37: ["8231&408293&3117", false],
38: ["1191&233598&77990", false],
40: ["6187&8888&33068", false],
48: ["560&227768&560", false],
64: ["864&968&1092", false],
65: ["873&977&2113", false],
66: ["991&866&2114", false],
67: ["2115&1995&2115", true],
68: ["6220&59589&876", true],
70: ["6222&499911&1110", true],
71: ["7111&11119&1111", true],
72: ["888&84424&6220", false],
80: ["790992&550000&66140", false],
96: ["1120&996&17776", true],
};
11&13&33
22&26&66
195&595&515
77&444&54
77&855&18213
223&3110&1190
3119&39111&9111
88&140&424
111&4777&8457
462&6666&794
111&6555&8795
6222&71500&444
77&855&18213|+00|88&140&424
82222&6223&331998
15|+00|15
280&592&528
3379&217&817
222&4114&4114
65559&955&65555
8221&88855&220
199991&133333&533333
22|+00|22
23|+00|21
888&999992&44440
88&140&424|+00|3379&217&817
462&6666&794|+00|280&592&528
11|+00|280&592&528|+00|11
4477&551966&844444
6222&71500&444|+00|3379&217&817
26|+00|22|+00|28
13|+00|31|+00|19
352&357&544
353&3173&553
354&554&550
355&555&555
444&3108&8228
8231&408293&3117
1191&233598&77990
33|+00|1191&233598&77990
6187&8888&33068
11&13&33|+00|6187&8888&33068
354&554&550|+00|88&140&424
355&555&555|+00|88&140&424
40|+00|44
11&13&33|+00|40|+00|44
44|+00|46|+00|06
11|+00|46|+00|44
560&227768&560
560&227768&560|+00|11&13&33
560&227768&560|+00|22&26&66
355&555&555|+00|280&592&528
560&227768&560|+00|77&444&54
444&3108&8228|+00|3379&217&817
354&554&550|+00|22|+00|22
55|+00|+55
560&227768&560|+00|88&140&424
3379&217&817|+00|6187&8888&33068
462&6666&794|+00|+560&227768&560
560&227768&560|+00|11|+00|11|+00
40|+00|280&592&528|+00|44
40|+00|3379&217&817|+00|44
62|+00|60
11|+00|62|+00|60
864&968&1092
873&977&2113
991&866&2114
2115&1995&2115
6220&59589&876
77&444&54|+00|873&977&2113
6222&499911&1110
7111&11119&1111
888&84424&6220
11&13&33|+00|888&84424&6220
22&26&66|+00|888&84424&6220
11|+00|864&968&1092|+00|11
77&444&54|+00|888&84424&6220
77&855&18213|+00|888&84424&6220
66|+00|+6222&71500&444|+00|68
77|+00|79|+00|11
790992&550000&66140
280&592&528|+00|873&977&2113
280&592&528|+00|991&866&2114
3379&217&817|+00|991&866&2114
6220&59589&876|+00|280&592&528
8221&88855&220|+00|873&977&2113
64|+00|22|+00|22|+00|+66
66|+00|21|+00|21|+00|+64
80|+00|88
88|+00|81|+00|09
22&26&66|+00|80|+00|88
11|+00|88|+00|91
77&444&54|+00|80|+00|88
85|+00|85|+00|88
22|+00|88|+00|84
95|+00|22|+00|79
1120&996&17776
1120&996&17776|+00|11&13&33
1120&996&17776|+00|22&26&66
354&554&550|+00|873&977&2113
77&444&54|+00|+1120&996&17776
ORigami
Now that we are properly "removing substrings", it is blindingly obvious what that is actually doing: Turning entire AND expressions into a single number. Put another way, we have discovered another expression form that works: a|b|c. Yes, in hindsight this should have been caught much earlier, but I was much more focused on speeding up substring removal that I never even thought about why.
At this point, I now have two pieces of code: an a&b&c expression finder, and an a|b|c expression finder. The latter is actually much nicer because the corresponding factor optimization -- where we remove any factors with extra bits instead of missing ones -- means our candidate list is absolutely tiny, never being greater than the number itself.
Using this new expression finder and taking the better of the two for each number gives us a 1914:
11&13&33
22&26&66
03|+00|03
04|+00|04
05|+00|05
06|+00|06
07|+00|07
08|+00|08
09|+00|09
02|+00|02|+00|08|+00|08
10|+00|11
04|+00|04|+00|08|+00|08
04|+00|04|+00|09|+00|09
06|+00|06|+00|08|+00|08
14|+00|15
280&592&528
3379&217&817
222&4114&4114
65559&955&65555
8221&88855&220
199991&133333&533333
20|+00|22
21|+00|23
888&999992&44440
88&140&424|+00|3379&217&817
462&6666&794|+00|280&592&528
08|+00|08|+00|18|+00|19
4477&551966&844444
6222&71500&444|+00|3379&217&817
04|+00|26|+00|28
30|+00|31
352&357&544
353&3173&553
354&554&550
355&555&555
444&3108&8228
8231&408293&3117
1191&233598&77990
34|+00|06|+00|+37
6187&8888&33068
11&13&33|+00|6187&8888&33068
354&554&550|+00|88&140&424
32|+00|10|+00|10|+00|+33
40|+00|44
41|+00|45
42|+00|46
43|+00|47
560&227768&560
560&227768&560|+00|11&13&33
560&227768&560|+00|22&26&66
355&555&555|+00|280&592&528
560&227768&560|+00|77&444&54
444&3108&8228|+00|3379&217&817
354&554&550|+00|22|+00|22
50|+00|+55
560&227768&560|+00|88&140&424
3379&217&817|+00|6187&8888&33068
462&6666&794|+00|+560&227768&560
560&227768&560|+00|11|+00|11
08|+00|44|+00|48|+00|48
08|+00|44|+00|49|+00|49
60|+00|62
61|+00|63
864&968&1092
873&977&2113
991&866&2114
2115&1995&2115
6220&59589&876
77&444&54|+00|873&977&2113
6222&499911&1110
70|+00|+71
888&84424&6220
11&13&33|+00|888&84424&6220
22&26&66|+00|888&84424&6220
11|+00|864&968&1092|+00|11
77&444&54|+00|888&84424&6220
77&855&18213|+00|888&84424&6220
66|+00|+6222&71500&444|+00|68
78|+00|79
790992&550000&66140
280&592&528|+00|873&977&2113
280&592&528|+00|991&866&2114
3379&217&817|+00|991&866&2114
6220&59589&876|+00|280&592&528
8221&88855&220|+00|873&977&2113
64|+00|20|+00|20|+00|+66
64|+00|20|+00|21|+00|+67
80|+00|88
81|+00|89
02|+00|82|+00|88
90|+00|91
04|+00|84|+00|88
04|+00|85|+00|89
06|+00|86|+00|88
94|+00|95
1120&996&17776
1120&996&17776|+00|11&13&33
1120&996&17776|+00|22&26&66
354&554&550|+00|873&977&2113
77&444&54|+00|+1120&996&17776
Then I modified my OR finder to incorporate AND expressions. It started with using 0, then tried using each one individually, then every combination of 2, etc. This netted us another 54 bytes down to an 1860.
A good example of an improvement is 25:
88&140&424|+00|3379&217&817 // Pure AND expression
280&592&528|+00|09|+00|09 // AND expression + OR expressions
More and more and more and more and more...
Getting inspired from my rewritten OR finder, I decided to sit down and do a better job creating an AND finder. Among other things, it:
- Can now check 4 factors (
a&b&c&d) or any arbitrary amount more - Expands the factor reduction to also remove any factors that fail in their radiated forms
- Expands the factor reduction to work across
&s (for example, if for a givenaandb, the expressiona&bproduces a number with missing bits, we skip checking anycordand advance to the nextb) - Improves our length check and allows it to skip more expressions (for example, if for a given
a&bwe already know the shortest expression is too long, we skip all the way to the nextasince we know all futurebs will be too long -- assuming the factors are sorted by length, of course!)
Checking up to 20,000,000, we get to a 56-number known array (which I call v2 due to splitting up the search), producing this 1754:
const known = { // n: [expr, firstOnly?] // 56 numbers v2
1: ["11&13&33", false],
2: ["22&26&66", false],
3: ["195&595&515", false],
4: ["77&444&54", true],
5: ["77&855&18213", false],
6: ["223&3110&1190", true],
7: ["3119&39111&9111", false],
8: ["88&140&424", false],
9: ["111&4777&8457", false],
10: ["462&6666&794", true],
11: ["111&6555&8795", true],
12: ["6222&71500&444", true],
14: ["82222&6223&331998", false],
16: ["280&592&528", false],
17: ["3379&217&817", false],
18: ["222&4114&4114", false],
19: ["65559&955&65555", false],
20: ["8221&88855&220", false],
21: ["855&733333&5799997", false],
24: ["888&999992&44440", false],
28: ["4477&551966&844444", false],
32: ["352&357&544", false],
33: ["353&3173&553", false],
34: ["354&554&550", true],
35: ["355&555&555", true],
36: ["444&3108&8228", false],
37: ["8231&408293&3117", false],
38: ["1191&233598&77990", false],
40: ["6187&8888&33068", false],
41: ["2097211&4808111&655977", false],
42: ["666666&53755&5997226", true],
43: ["2555&664111&2555&664111", true],
48: ["560&227768&560", false],
49: ["8893&1999931&808817", false],
56: ["8888&7919929&888888", false],
64: ["864&968&1092", false],
65: ["873&977&2113", false],
66: ["991&866&2114", false],
67: ["2115&1995&2115", true],
68: ["6220&59589&876", true],
69: ["1117&2209997&4855", false],
70: ["6222&499911&1110", true],
71: ["7111&11119&1111", true],
72: ["888&84424&6220", false],
73: ["6233&2655979&2555977", true],
74: ["6223&82666&4337754", true],
76: ["6220&4326221&4522220", true],
78: ["6222&2139998&4522222", true],
80: ["882&7253&2116696", false],
81: ["891&8884435&2133333", false],
82: ["15990995&4799954&8556666", false],
84: ["2933342&4794455&2229332", false],
85: ["2933333&4794455&2229333", false],
96: ["1120&996&17776", true],
97: ["17777&11549413&2228331", false],
98: ["998&4450426&998&4450426", false],
};
11&13&33
22&26&66
03|+00|03
04|+00|04
05|+00|05
06|+00|06
07|+00|07
08|+00|08
09|+00|09
462&6666&794
10|+00|11
6222&71500&444
04|+00|04|+00|09|+00|09
82222&6223&331998
14|+00|15
280&592&528
3379&217&817
222&4114&4114
65559&955&65555
8221&88855&220
855&733333&5799997
20|+00|22
21|+00|23
888&999992&44440
280&592&528|+00|09|+00|09
222&4114&4114|+00|08|+00|08
08|+00|08|+00|18|+00|19
4477&551966&844444
8221&88855&220|+00|09|+00|09
04|+00|26|+00|28
30|+00|31
352&357&544
353&3173&553
354&554&550
355&555&555
444&3108&8228
8231&408293&3117
1191&233598&77990
37|+00|+34|+00|06
6187&8888&33068
2097211&4808111&655977
666666&53755&5997226
2555&664111&2555&664111
40|+00|44
41|+00|45
42|+00|46
43|+00|47
560&227768&560
8893&1999931&808817
22&26&66|+00|560&227768&560
355&555&555|+00|280&592&528
560&227768&560|+00|04|+00|04
560&227768&560|+00|05|+00|05
352&357&544|+00|20|+00|22
55|+00|+50
8888&7919929&888888
560&227768&560|+00|09|+00|09
462&6666&794|+00|560&227768&560
560&227768&560|+00|10|+00|11
08|+00|44|+00|48|+00|48
08|+00|44|+00|49|+00|49
60|+00|62
61|+00|63
864&968&1092
873&977&2113
991&866&2114
2115&1995&2115
6220&59589&876
1117&2209997&4855
6222&499911&1110
71|+00|+70
888&84424&6220
6233&2655979&2555977
6223&82666&4337754
6223&82666&4337754|+00|11
6220&4326221&4522220
6220&59589&876|+00|09|+00|09
6222&2139998&4522222
78|+00|79
882&7253&2116696
891&8884435&2133333
15990995&4799954&8556666
3379&217&817|+00|991&866&2114
2933342&4794455&2229332
2933333&4794455&2229333
66|+00|+64|+00|20|+00|20
67|+00|+65|+00|20|+00|20
80|+00|88
81|+00|89
02|+00|82|+00|88
90|+00|91
04|+00|84|+00|88
04|+00|85|+00|89
06|+00|86|+00|88
94|+00|95
1120&996&17776
17777&11549413&2228331
998&4450426&998&4450426
33|+00|+32|+00|991&866&2114
1120&996&17776|+00|04|+00|04
The Last Bit
At this point, the hole had been out for around 3 months, so naturally myself, Bulmenisaurus, and Luke (the 3 JavaScript contenders with scores on the board at this point) started dropping subtle hints in the Byte Heist Discord. With these, I realized there was another search space we were missing: What about decimal numbers?
One week of bruteforce later, we find... a whole two 1-byte saves!
81: ["891&8884435&2133333", false],
81: ["891&8884437.1&7633", false],
97: ["17777&11549413&2228331", false],
97: ["997&2678897.1&8433771", false],
The future is now. Anyway, we also decided to drop the lengths of our expressions. With this, I discovered two things:
- They are way ahead of me (both sitting around 1200-1300 while I'm in the mid 1700s), with their maximum expressions being 16 bytes but mine 31.
- Their 1-9 expressions are all length 6, but mine are 8 or 9!
Length 6 is short enough that it can be bruteforced with raw eval()s (more on this in the appendix). Indeed, a short amount of bruteforcing later tells us the magic formula:
01||01
02||02
03||03
04||04
05||05
06||06
07||07
08||08
09||09
Honestly, it's genius, and they both probably just thought of it. It is very similar to the ones I found with my OR finder, e.g. 03|+00|03. For some reason it never occurred to me to try removing those middle bytes; perhaps I was weary of any more substring removal projects given my earlier attempts?
With these 2 small improvements, we get to 1727:
01||01
02||02
03||03
04||04
05||05
06||06
07||07
08||08
09||09
462&6666&794
10|+00|11
6222&71500&444
04|+00|04|+00|09|+00|09
82222&6223&331998
14|+00|15
280&592&528
3379&217&817
222&4114&4114
65559&955&65555
8221&88855&220
855&733333&5799997
20|+00|22
21|+00|23
888&999992&44440
280&592&528|+00|09|+00|09
222&4114&4114|+00|08|+00|08
08|+00|08|+00|18|+00|19
4477&551966&844444
8221&88855&220|+00|09|+00|09
04|+00|26|+00|28
30|+00|31
352&357&544
353&3173&553
354&554&550
355&555&555
444&3108&8228
8231&408293&3117
1191&233598&77990
37|+00|+34|+00|06
6187&8888&33068
2097211&4808111&655977
666666&53755&5997226
2555&664111&2555&664111
40|+00|44
41|+00|45
42|+00|46
43|+00|47
560&227768&560
8893&1999931&808817
22&26&66|+00|560&227768&560
355&555&555|+00|280&592&528
560&227768&560|+00|04|+00|04
560&227768&560|+00|05|+00|05
352&357&544|+00|20|+00|22
55|+00|+50
8888&7919929&888888
560&227768&560|+00|09|+00|09
462&6666&794|+00|560&227768&560
560&227768&560|+00|10|+00|11
08|+00|44|+00|48|+00|48
08|+00|44|+00|49|+00|49
60|+00|62
61|+00|63
864&968&1092
873&977&2113
991&866&2114
2115&1995&2115
6220&59589&876
1117&2209997&4855
6222&499911&1110
71|+00|+70
888&84424&6220
6233&2655979&2555977
6223&82666&4337754
6223&82666&4337754|+00|11
6220&4326221&4522220
6220&59589&876|+00|09|+00|09
6222&2139998&4522222
78|+00|79
882&7253&2116696
891&8884437.1&7633
15990995&4799954&8556666
3379&217&817|+00|991&866&2114
2933342&4794455&2229332
2933333&4794455&2229333
66|+00|+64|+00|20|+00|20
67|+00|+65|+00|20|+00|20
80|+00|88
81|+00|89
02|+00|82|+00|88
90|+00|91
04|+00|84|+00|88
04|+00|85|+00|89
06|+00|86|+00|88
94|+00|95
1120&996&17776
997&2678897.1&8433771
998&4450426&998&4450426
33|+00|+32|+00|991&866&2114
1120&996&17776|+00|04|+00|04
(Edit 1 month after problem but I haven't looked at the others' solutions yet) It's been a while since I looked at this problem, but I found a few more saves:
- My OR finder was still checking
a|+00|b, but I realized we can simply checka|b|cand add 0 and 00 as factors (-100 bytes) - A further improvement to the OR finder which I'm not entirely sure what I did (-54 bytes), and then another -6 bytes from running it for longer
- "59 and 75 improvement from improvements to
a|b|cregarding testing forced octal and forced decimal numbers" (-10 bytes) - Checking "double 0 numbers" (e.g. 0049) and "00n" numbers (-49 bytes)
- More a&b&c factor running for a 67-number known (-17 bytes)
- Length 4 1-9 (-18 bytes)
Let me expand on that last one. Luke told us that he had found length 4 1-9, which shocked me because I thought I had run my eval bruteforcer on everything up to and including length 6. But I was making some assumptions to speed it up, and as it turns out, there's a symbol that's really helpful: ;. The numbers are of the form n;;n. It's honestly genius!
This leads to my final score of 1473 and a 67-number known:
const known = { // n: [expr, firstOnly?] // 67 numbers
1: ["11&13&33", false],
2: ["22&26&66", false],
3: ["195&595&515", false],
4: ["77&444&54", true],
5: ["77&855&18213", false],
6: ["223&3110&1190", true],
7: ["3119&39111&9111", false],
8: ["88&140&424", false],
9: ["111&4777&8457", false],
10: ["462&6666&794", true],
11: ["111&6555&8795", true],
12: ["6222&71500&444", true],
13: ["99997&0575&004155", false],
14: ["82222&6223&331998", false],
16: ["280&592&528", false],
17: ["3379&217&817", false],
18: ["0662&223&826", false],
19: ["65559&955&65555", false],
20: ["8221&88855&220", false],
21: ["855&221333&00277", false],
22: ["7991&222&7991&222", false],
24: ["00331&88888&888", false],
25: ["028473&00377&00331", false],
26: ["00333&711994&0173338", false],
27: ["00333&711995&00173339", false],
28: ["4477&551966&844444", false],
32: ["352&357&544", false],
33: ["353&3173&553", false],
34: ["354&554&550", true],
35: ["355&555&555", true],
36: ["444&3108&8228", false],
37: ["8231&408293&3117", false],
38: ["00477&1190&77990", false],
39: ["3111&5111&079911", true],
40: ["0558&33704&440", false],
41: ["0559&0571&0751", false],
42: ["00572&871466&666666", false],
43: ["2555&664111&2555&664111", true],
44: ["444&17724&42220&0556", true],
48: ["560&00760&560", false],
49: ["8817.7&8817&002673", false],
50: ["00662&08822&08826", false],
52: ["00665&847991&847988", false],
54: ["0766&00666&47991&661110", false],
56: ["00772&888888&8888", false],
64: ["864&968&1092", false],
65: ["873&977&2113", false],
66: ["991&866&2114", false],
67: ["2115&1995&2115", true],
68: ["6220&59589&876", true],
69: ["1117&2209997&4855", false],
70: ["6222&499911&1110", true],
71: ["7111&11119&1111", true],
72: ["888&84424&6220", false],
73: ["84431&01515&01131", false],
74: ["001132&95466&6222", false],
76: ["6220.4&6221&01356", true],
78: ["6222&2139998&4522222", true],
80: ["882&7253&2116696", false],
81: ["891&8884437.1&7633", false],
82: ["15990995&4799954&8556666", false],
84: ["2933342&4794455&2229332", false],
85: ["2933333&4794455&2229333", false],
88: ["888&0521336&84440", false],
96: ["1120&996&17776", true],
97: ["997&2678897.1&8433771", false],
98: ["998&4450426&998&4450426", false],
};
1;;1
2;;2
3;;3
4;;4
5;;5
6;;6
7;;7
8;;8
9;;9
462&6666&794
10|+00|11
6222&71500&444
0015|+00|0014
06|+08|+06|+08
14|+00|15
280&592&528
3379&217&817
0662&223&826
0023|+00|0021
8221&88855&220
855&733333&5799997
20|+00|22
21|+00|23
00331&88888&888
08|3379&217&817|009
0022|+08|+0020|+08
0033|+00|0030
4477&551966&844444
0014|3379&217&817|0015
28|+00|04|+26
30|+00|31
352&357&544
353&3173&553
354&554&550
355&555&555
444&3108&8228
0045|+00|0041
0046|+00|0042
35|+00|0046
0558&33704&440
08|353&3173&553|009
00572&871466&666666
33|+10|+32|+10
40|+00|44
41|+00|45
42|+00|46
43|+00|47
560&227768&560
8893&1999931&808817
00662&08822&08826
0022|+32|+0020|+33
00665&847991&847988
5.2|05|560&227768&560
0066|+00|0060
55|+00|+50
00772&888888&8888
1.6|01|00772&888888&8888
2.4|02|00772&888888&8888
032|+32|+032|+33
48|+08|+48|+00|44
49|+08|+48|+00|45
60|+00|62
61|+00|63
864&968&1092
873&977&2113
991&866&2114
2115&1995&2115
6220&59589&876
1117&2209997&4855
66|+04|+64|+04
71|+00|+70
888&84424&6220
6233&2655979&2555977
001132&95466&6222
11|864&968&1092|0013
6220&4326221&4522220
0015|864&968&1092|0015
68|+08|+04|+08|+66
78|+00|79
882&7253&2116696
891&8884437.1&7633
0022|864&968&1092|0022
0023|+864&968&1092|0023
2933342&4794455&2229332
2933333&4794455&2229333
66|+20|+64|+20
71|+16|+70|+16
80|+00|88
81|+00|89
88|+2.4|82
90|+00|91
84|+00|04|+88
85|+00|04|+89
88|+6.4|86
94|+00|95
1120&996&17776
997&2678897.1&8433771
998&4450426&998&4450426
1120&996&17776|3.2|03
0044|864&968&1092|0044
What's Next?
There are a few ideas I have for ways to improve:
- Check octal numbers (
0123), octal numbers again (0o123), binary numbers, hexadecimal numbers, and scientific notation - Check XOR
^expressions (since this can both add and remove bits, we cannot do any factor optimization which will make this run very slow) - Get a supercomputer to expand our AND search
- pysearch
The biggest issue I see with these is that they are unlikely to provide more than small incremental improvements. I am reasonably certain that both Luke and Bulmen have found a more general form that works for all numbers, no "combinations" needed. Even more shockingly, Luke mentioned finding a few scientific notation ties, implying large numbers, but he also has a jaw-droppingly nice 69 bytes on the generator problem, implying it's possible to make a generator that's extremely simple and fast. It seems to me I need a new strategy for generating these expressions.
Or I could also look at Luke and Bulmen's solutions, since I wrote this draft so long ago that the solution is now in post-mortem...
Appendix
(Maybe I will fill these in someday...?)
Top comments (0)