Uno de los paradigmas de programación menos conocidos que parece más adecuado para el golf de código es la programación orientada a la superposición (OOP) *. Al escribir código parcialmente idéntico, se pueden guardar muchos bytes simplemente superponiendo las partes idénticas y recordando de alguna manera dónde comienzan las dos líneas de código originales. Su tarea es escribir dos programas o funciones superpuestoscompress
y decompress
con la siguiente especificación:
* No usar en código de producción, probablemente.
compress
compress
toma dos cadenas en cualquier formato conveniente y las superpone tanto como sea posible. Es una cadena s
con una longitud mínima que se devuelve de manera que ambas cadenas de entrada son subcadenas de s
. Además, se devuelve alguna salida que identifica los índices de inicio y finalización de ambas cadenas.
Ejemplos: (El formato IO exacto depende de usted)
compress("abcd", "deab") -> "deabcd" ((2,5),(0,3))
compress("abcd", "bc") -> "abcd" ((0,3),(1,2))
compress("abc", "def") -> "abcdef" ((0,2),(3,5)) or "defabc" ((3,5),(0,2))
decompress
decompress
calcula la función inversa de compress
, que se le da una cadena y dos índices de inicio y fin (en el formato en el que los devuelve compress
), devuelve las dos cadenas originales. Solo necesita manejar entradas válidas. El siguiente igualdad debe mantener para todas las cadenas s1
, s2
:
(s1, s2) == decompress (compress (s1, s2))
Ejemplos: (inversos de compress
ejemplos)
decompress "deabcd" ((2,5),(0,3)) -> "abcd" "deab"
decompress "abcd" ((0,3),(1,2)) -> "abcd" "bc"
decompress "abcdef" ((0,2),(3,5)) -> "abc" "def"
or (whichever version your "compress" generates)
decompress "defabc" ((3,5),(0,2)) -> "abc" "def"
Tanteo
Su puntaje es el tamaño de la cadena devuelta al llamar compress("<code of compress>", "<code of decompress>")
. Como se trata de código de golf, una puntuación más baja es mejor.
Ejemplo:
Suponga que el código para su función compress
es c=abcd
y el código para decompress
es d=efghi
. Luego, los compress("c=abcd", "d=efghi")
rendimientos "c=abcd=efghi"
(y los índices, pero no afectan la puntuación), entonces la puntuación es length "c=abcd=efghi" = 12
.
Reglas Adicionales
- En el espíritu de este desafío, tu
compress
ydecompress
debes superponerse en al menos un personaje. Puede lograr esto de manera trivial agregando un comentario, pero tenga en cuenta que hacerlo aumentará su puntaje y puede haber soluciones más cortas usando un código inherentemente superpuesto. compress
ydecompress
debería poder manejar cadenas que contengan caracteres ASCII imprimibles, así como todos los caracteres que utilizó para definircompress
ydecompress
.- Los índices pueden estar indexados a cero o uno.
- Sus programas o funciones no tienen que ser nombrados
compress
ydecompress
.
Respuestas:
GNU Prolog, 105 puntos
(Esto requiere GNU Prolog porque
prefix
ysuffix
no son portátiles).Prolog tiene una gran ventaja interesante para este desafío; puede escribir una función para manejar múltiples patrones de llamada (es decir, no solo puede darle a la función una entrada para obtener una salida correspondiente, sino que también puede darle a la función una salida para obtener la entrada correspondiente). Como tal, podemos definir una función que pueda manejar tanto la compresión como la descompresión, lo que lleva a un envío de 105 bytes que define una función
o
que funciona en ambos sentidos. (Por cierto, lo escribí principalmente como un descompresor, ya que es más simple, y obtuve el compresor "gratis"). En general, podríamos esperar un programa muy corto en Prolog para esta tarea, si no es por el hecho de que es tan malo en el manejo de cadenas (tanto en términos de primitivas faltantes como en términos de primitivas en cuestión que tienen nombres terriblemente largos).El primer argumento
o
es una tupla de cadenas, por ejemplo"abcd"-"deab"
. El segundo argumento tiene una forma como"deabcd"-4/6-4/4
; Esta es una tupla anidada bastante estándar, y significa que la cadena está "desacreditada", la primera cadena tiene longitud 4 y termina en el sexto carácter, la segunda cadena tiene longitud 4 y termina en el cuarto carácter. (Tenga en cuenta que una cadena en GNU Prolog es solo una lista de códigos de caracteres, lo que hace que la depuración sea molesta porque la implementación prefiere la última interpretación de forma predeterminada).o
un argumento, generará el otro para usted (por lo tanto, funciona como un compresor si le da el primer argumento, y un descompresor si le da el segundo). Si le da ambos argumentos, verificará que la representación comprimida coincida con las cadenas dadas. Si le da cero argumentos, generará resultados como este:La descripción anterior del formato de E / S es prácticamente solo una descripción del programa, también; no hay mucho en el programa en absoluto. La única sutileza tiene que ver con las sugerencias de orden de evaluación; debemos asegurarnos de que el programa no solo use una estrategia de búsqueda que garantice la terminación, sino que también produzca la cadena de salida más corta posible.
Al comprimir, comenzamos con
length(C,_)
("C
tiene una longitud"), que es un truco que he usado en muchas respuestas de Prolog y Brachylog; Si esto es lo primero que ve Prolog, hará que priorice la reducción de la duración deC
cualquier otra cosa. Esto asegura que tengamos una longitud mínimaC
. El orden de las restricciones ens
se elige cuidadosamente para que la búsqueda tome un tiempo finito para cada posible candidato de longitudC
;A
está restringido porC
(no sabemosC
, pero sí sabemos el valor objetivo que tenemos para su longitud),M
porA
,U
porA
yL
porU
, por lo que ninguna de las búsquedas puede tomar tiempo ilimitado.Al descomprimir,
C
el usuario nos da directamente. Esto nuevamente asegura que el programa se ejecutará en un tiempo finito, debido a la misma secuencia de restricciones. (Las personas que son conscientes de orden de evaluación de Prolog se tenga en cuenta que la definición des
es muy ineficiente cuando se descomprime; colocarlength(A,M)
ylength(U,L)
primera sería más rápido, pero moviéndoselength(A,M)
al inicio podría provocar un bucle infinito cuando se comprime porque niA
tampocoM
está obligado por nada en el momento .)fuente
Brachylog ,
5046 bytesPruébalo en línea!
Descomprimir:
Pruébalo en línea!
Guardado 5 bytes gracias a @ ais523
Explicación
El lado bueno de los lenguajes declarativos es que podemos reutilizar el mismo código para comprimir y descomprimir. Como tal, el código para comprimir es exactamente el mismo que para descomprimir , con un adicional
~
al principio.Esto
~
le dice a Brachylog que invierta el orden de los argumentos (es decir, use la Entrada como salida y la Salida como entrada). Como comprimir no tiene~
, en realidad ejecuta el predicado en el orden estándar. Como descompress tiene solo uno, lo ejecuta con Input como output y Output como input.De esa manera, podemos usar el mismo código (módulo adicional
~
) para comprimir y descomprimir: la compresión proporciona las dos cadenas como entrada y una variable como salida, y la descompresión proporciona los índices y la cadena comprimida como salida y una variable como Entrada .Obviamente, esto también significa que tenemos que ser un poco explícitos acerca de nuestro código de compresión, para que el intérprete sea capaz de ejecutarlo "hacia atrás". Es por eso que el compresor en sí es un poco largo.
Aquí hay un desglose del código para Comprimir (y, por lo tanto, también para descomprimir):
fuente
Gelatina ,
5850 bytes-1 byte gracias a ais523 (uso
⁾
para una cadena de dos bytes)Esto bien puede ser bastante golfable ...
La compresión toma dos argumentos de cadena y devuelve una lista:
[[[startA, lengthA], [startB, lengthB]], compressedString]
La descompresión toma un argumento (tal lista) y devuelve dos cadenas *:
Código superpuesto:
Un índice.
* esto puede no ser obvio debido al formato de impresión implícito de Jelly, por lo que el código en TryItOnline vinculado a arriba tiene un byte adicional (
Y
a al final) para insertar un avance de línea entre los dos en la salida impresa.Comencé con un solo programa, que utilizaba la profundidad del primer (o único) argumento para decidir entre compresión y descompresión, pero tener un enlace no utilizado en el código de descompresión (la primera línea) y un solo byte superpuesto es más corto en siete bytes. .
¿Cómo?
fuente
“ṫḣ”
se puede jugar golf por 1 byte usando la sintaxis de Jelly para cadenas de 2 caracteres.