Dado un número, determine si es un número plegable.
Un número plegable es un número tal que si lo toma como representación binaria y lo "dobla" por la mitad, es decir, toma el resultado de la multiplicación XNOR de la primera mitad del número y la segunda mitad con los dígitos en reversa, obtendrá cero.
Si el número tiene un número impar de dígitos en binario, su dígito central debe ser 1 y se ignora al plegar.
Como eso puede ser un poco confuso, daré algunos ejemplos:
178
La representación binaria de 178 es
10110010
Para doblar esto, primero lo dividimos por la mitad
1011 0010
Revertimos la segunda mitad
1011
0100
Y nosotros XNOR las dos mitades:
0000
Esto es cero, así que este es un número plegable.
1644
La representación binaria de 1644 es
11001101100
Para doblar esto, primero lo dividimos por la mitad
11001 1 01100
El bit medio es 1, así que lo tiramos.
11001 01100
Revertimos la segunda mitad
11001
00110
Y nosotros XNOR las dos mitades:
00000
Esto es cero, así que este es un número plegable.
4254
La representación binaria de 4254 es
1000010011110
Para doblar esto, primero lo dividimos por la mitad
100001 0 011110
El bit del medio es 0, por lo que este no es un número plegable.
Tarea
Su tarea es tomar un número positivo y devolver un verdadero si el número es plegable y falso si no lo es. Este es el código de golf, así que trate de mantener la cuenta regresiva de bytes.
Casos de prueba
Aquí están los primeros 99 números plegables:
[1, 2, 6, 10, 12, 22, 28, 38, 42, 52, 56, 78, 90, 108, 120, 142, 150, 170, 178, 204, 212, 232, 240, 286, 310, 346, 370, 412, 436, 472, 496, 542, 558, 598, 614, 666, 682, 722, 738, 796, 812, 852, 868, 920, 936, 976, 992, 1086, 1134, 1206, 1254, 1338, 1386, 1458, 1506, 1596, 1644, 1716, 1764, 1848, 1896, 1968, 2016, 2110, 2142, 2222, 2254, 2358, 2390, 2470, 2502, 2618, 2650, 2730, 2762, 2866, 2898, 2978, 3010, 3132, 3164, 3244, 3276, 3380, 3412, 3492, 3524, 3640, 3672, 3752, 3784, 3888, 3920, 4000, 4032, 4222, 4318, 4462, 4558]
0
, así que no. (Sin embargo, podría valer la pena tener un tercer ejemplo trabajado como este). Lo mismo ocurre con 18.Respuestas:
Jelly, 9 bytes
Try it online! or verify all test cases.
How it works
fuente
05AB1E,
1312 bytesCode:
Uses the CP-1252 encoding. Try it online!
Explanation:
First, we convert the number to binary using
b
. 1644 becomes 11001101100. We split this into two pieces with2ä
. For example, 11001101100 would become:If there is an uneven number of bits, the first part will receive the extra bit. We
R
everse the last string and append a zero using0¸«
. The reason for this is to only give truthy results when the middle bit is a 1 (1 XOR 0 = 1 and 0 XOR 0 = 0). If there is no middle bit, 05AB1E will just ignore the last bit (the zero that was appended) :The last thing we need to do is do an element-wise XOR and take the product of the result. If there is one element too many, the program will just leave the last element out (
[1, 0, 0] XOR [0, 1] = [1, 1]
) For example:Becomes:
And the product of that is 1, which is truthy.
fuente
s
is required.bÐg;ô
was as far as I got before refreshing and seeing you nailed it. Great answer, helping me learn!Java 7,
152 145 142 138134 bytesLoops over the string like it would for a palindrome, looking for zeroes. Keeps track by repeatedly multiplying, so all you have to do is check that it's not zero at the end.
Without scroll bars:
fuente
byte[]b=(a+"").getBytes();
is shorter than thechar[]b=a.toString(a,2).toCharArray();
and still seems to work (-12 bytes).getBytes
might still work over the char[]. Thanks :)z
as an int (0
for falsy, any other for truthy) - will save you a couple of bytes.JavaScript (ES6),
615752 bytesRecursively computes:
where
N
is the rank of the highest bit set in the input.If the input has an odd number of bits, the middle bit is XOR'ed with undefined (the value returned by
pop()
on an empty array), which lets it unchanged. So, a0
middle bit clears the output and a1
middle bit doesn't alter the result of the other operations -- which is consistent with the challenge definition of a folding number.fuente
Python 2, 57 bytes
Outputs via exit code: error for Falsey, and no error for Truthy.
Converts the input into binary. Checks whether the first and last character are unequal, keeps and repeating this after removing those characters.
The comparison
s[-1]==s[0]<_
gives an error if the first and last character are unequal by trying to evaluate the unassigned variable named_
. If they are equal, the chain of inequalities is short-circuited instead. When we get to the middle element of1
, thewhile
loop is terminate to special-case it as OK.I suspect a purely arithmetic approach will be shorter with a recursion like
f=lambda n,r=0:...f(n/2,2*r+~n%2)...
to chomp off binary digits from the end flipped and reversed, and detect whenn
andr
are equal up to a center1
. There are subtleties though with leading zeroes and the center.fuente
Python 2,
94 79 7267 bytesSaved 12 bytes thanks to @xnor
Defines an unnamed function on the second line.
Explanation (with some whitespace added):
Try it here!
fuente
s==''or s=='1'
can bes in'1'
and
can be arithmetic*
. Also,f
is allowed to be unnamed.Haskell,
898886 bytesWorks by summing bitwise the bit representation with its reverse and taking the product. If it's 1 or 2, the number is a folding number (1 if there are even bits that fold, 2 if there are odd bits and a one in the middle).
fuente
Python 2,
100999594 BytesThis feels a bit long, but I'll keep working at it :) Prints a
1
if the number can be folded,0
otherwise.Test it here!
thanks to Wheat Wizard for the 1-byte save :)
thanks to Rod for the 5-byte save! :)
fuente
b-1
with~b
[1,a[b]>'0'][len(a)%2]
with(a[b]>=`len(a)%2`)
e=len(a)
to changeb=e/2
`e%2
` , saving 1 byte. And then both python answer will be tied c:><>, 37+3 = 40 bytes
Input is expected to be present on the stack at program start, so +3 bytes for the
-v
flag.Try it online!
fuente
Jelly, 13 bytes
TryItOnline
Or matching terms up to 4558
How?
fuente
Perl, 46 bytes
Includes +1 for
-p
Run with the number on STDIN
folding.pl
:I consider it a perl bug that this even works. Internal
$_
should not be getting match position updates once it is modified. In this program the match position actually moves beyond the end of$_
fuente
perl -pe '$_=sprintf("%b",$_)=~/^(.*)1?(??{reverse$^N=~y%01%10%r})$/'
:/Brachylog, 16 bytes
It doesn't quite work online...
Takes input through the input variable and outputs through success or failure. It relies heavily on
z₂
, which has been in the language since April 30, but we forgot to ask to have it pulled on TIO so for the time being this only works on a local installation of the language. Either way it's probably an overly naive approach.Brachylog (on TIO), 19 bytes
Try it online!
lᵛ↖Lz
is functionally equivalent toz₂
(if you don't use the variable L anywhere else), but it's also three bytes longer.fuente
Python 2,
76 7169 bytes-5 bytes thanks to @Dennis (
''
is present in'1'
, so replacein('','1')
within'1'
)-2 bytes thanks to @xnor (use multiplication,
(...)*
in place ofand
)Ideone
Recursive function, upon first call
n
is a number so it evaluates as less than the empty string, withif n<''
, and the function is called again but withn
cast to a binary string; the tail is either an empty string (even bit-length) or the middle bit, which returns true for empty or a'1'
; on it's way down it tests the outer bits for inequality (equivalent to XOR) and recurses on the inner bits,n[1:-1]
.fuente
n in'1'
works.''
was present in'blah'
, but yes it is :)and
can be arithmetic*
.Python 2, 63 bytes
Prints
True
orFalse
. Takes the binary representation ofs
and repeatedly removed the first and last characters as long as they are unequal. Checks whether what remains is the empty string or a central1
. This is done by converting''
to'1'
and checking if the result equals'1'
, which also avoid an index error on the empty string.fuente
PowerShell v2+, 143 bytes
Two possible approaches, both the same byte count.
Method 1:
Takes input
$n
, if it's-eq
ual to1
(a special case for this algorithm), increment it. Set$o
utput to be1
(i.e., assume truthy), then loop from0
to the midway point of the input number that has been[convert]
ed to binary. Note the-!($b%2)
to account for odd length binary numbers.Each iteration, we compare the current digit
$n[$_]
with the digit the same length from the end$n[$b-$_]
, and multiply the Boolean result into$o
(essentially performing an-and
on all of them). Once the loop is done, we need to potentially account for the middle binary digit, that's the pseudo-ternary at the end (array indexed via$b%2
). That1
or0
is left on the pipeline, and output is implicit.Method 2:
Takes input and does the same process to
[convert]
the number to binary. Then we're in afor
loop so long as the.length
of the binary string is-g
reatert
han2
. When we're in the loop, if the first$n[0]
and last$n[-1]
digits are-n
ote
qual, slice those two digits off of$n
and re-store it into$n
. Otherwise, output0
andexit
. Once we're out of the loop, we either have (an array of1
,1,0
,0,1
,1,1
, or0,0
), or the binary string for two10
, or 311
. So, we need to test those two possibilities. For the first, we-join
$n
together with+
and evaluate the result and test that it's1
(this is true for arrays1
,1,0
, and0,1
, but is$false
for arrays0,0
and1,1
or strings10
or11
). The other half of the-or
is testing whether$n
is-eq
ual to10
(i.e., input of2
). That Boolean is left on the pipeline, and output is implicit.fuente
CJam, 13 bytes
Try it online! or generate a list of folding numbers up to a given number.
fuente
MATL, 16 bytes
Truthy is an array with all ones. Check truthy/falsy criteria here.
Try it online! Or Verify the first 20 test cases.
Explanation
Let's use input
1644
as an example.fuente
PHP, 101 Bytes
or with log
108 Bytes with array
True values <10000
fuente
Julia, 66 bytes
My first golf! works the same way as the Python solution of the same length, minor differences due to language (I did come up with it on my own, though...).
Explanation:
fuente
C,
223201189194178 BytesBrute force algorithm. Let's see how far it can be golfed.
Better test setup bugfixes...
fuente
MATL, 13 bytes
Truthy is an array with all ones. Check truthy/falsy criteria here.
Try it online! Or verify the first 20 test cases.
Explanation
Using input
1644
as an example:fuente
JavaScript, 71 bytes
Defines an anonymous function.
This method may not be the shortest, but as far as I know, it is unique. It adds the number in binary to itself reversed, treating them as decimal, then checking if the result is valid using a regex.
fuente
Retina, 92 bytes
Byte count assumes ISO 8859-1 encoding.
Try it online
Convert to unary. Convert that to binary. Cut the number in half and remove a middle
1
if there is. Reverse the first half. Switch its ones and zeros. Match if both halves are equal.fuente
Retina,
717060 bytesI probably still have a lot to learn about Retina (e.g. recursive regex?). Explanation: Step 1 converts from decimal to unary. Step 2 converts from unary to pseudo-binary. Step 3 removes digits from both ends as long as they mismatch. Step four matches an optional final central 1 if necessary. Edit: Saved 1 byte thanks to @mbomb007. Saved 10 bytes by improving my unary to binary conversion.
fuente
.*
or.+
.Python 2,
6159 bytesSaving two bytes for converting shifts to multiplications
Returns
0
for a folding number and anything else for non-folding. Uses the bit-twiddling approach.fuente
C,
6563 bytesTwo bytes for converting shifts to multiplications
Whitespace is already excluded from bytecount, returns 0 for a folding number and anything else for non-folding. Uses the bit-twiddling approach.
fuente
k, 77 bytes
by way of explanation, a translation to
q
fuente