Cuerdas de golf en Fourier

24

Reto

Dada una cadena como entrada, baje el programa Fourier que genera esa cadena.

En Fourier no hay una manera fácil de generar una cadena: debe pasar por cada código de carácter y generarlo como un carácter.

Fourier

El lenguaje se basa en un acumulador, una variable global que se inicializa a 0 al inicio del programa. Esto es utilizado por casi todos los operadores en el idioma. Solo algunos no cambian el valor del acumulador.

Personaje fuera

a

Toma el valor del acumulador como el código ASCII y genera el carácter. No cambia el valor del acumulador.

Si el acumulador es mayor que 255, el programa devolverá un error. Del mismo modo, si el acumulador es menor que 0.

Número fuera

o

Emite el valor del acumulador. No cambia el valor del acumulador.

Incrementar

^

Aumentar el acumulador en uno.

Disminución

v

Disminuya el acumulador en uno.

Añadir

+x

Establece el acumulador en el valor del acumulador más el valor de x.

Sustraer

-x

Establece el acumulador en el valor del acumulador menos el valor de x.

Multiplicar

*x

Establece el acumulador en el valor del acumulador multiplicado por el valor de x.

Dividir

/x

Establece el acumulador en el valor del acumulador dividido por el valor de x. (Tenga en cuenta que esta es una división entera, por lo que 1/6resulta en 0)

Número

n

Establezca el acumulador en el entero n.

Nota

Aquí, xy npuede ser cualquier número entero desde 0hasta 2^32-1inclusivo.

Más información

Solo debe usar los operadores descritos anteriormente. Por lo tanto, su programa de Fourier generado no es válido si utiliza cualquiera de los siguientes (tenga en cuenta que los siguientes operadores están autorizados para la recompensa):

  • Repetir bucles
  • Si las declaraciones
  • Variables
  • Aleatorio
  • Módulo
  • Entrada del usuario
  • Mayor / menor que los operadores
  • Operadores de igualdad
  • Pantalla clara
  • Tiempo de retardo
  • Funciones de fecha

Su programa puede ser un programa completo o una función, tomando entrada a través de STDIN, un archivo o argumentos de función. También puede recibir información directamente de Internet.

Tenga en cuenta que si hay un vvcódigo en su código, debe reemplazarlo por -2. Lo mismo ocurre ^^, reemplazándolo con +2.

Ejemplos

Si la entrada es 7n, entonces el programa esperado es:

55a110a

Pero puedes guardar un byte con

55a*2a

Otra forma es

7o110a

Usando número fuera.


Del mismo modo, si la entrada es Hello, entonces el programa esperado es:

72a101a108a108a111a

Puede reducirlo en 3 bytes (porque la salida no cambia el acumulador):

72a101a108aa111a

Pero espera, podemos usar el operador de suma, ahorrando 2 bytes:

72a101a+7aa+3a

Formateo

Como usaré la tabla de clasificación de Stack Snippet de Martin Büttner, por favor, ¿podría formatear el título de esta manera?

# <Language name>, <length of total output> bytes

Luego, puede poner lo que desee debajo del título.

Victorioso

Debe publicar la longitud de los programas de Fourier (producidos por su código) para generar este archivo de texto y este archivo de texto . Su puntaje es la longitud combinada de ambos programas de Fourier en bytes (los caracteres no ASCII no se usan en Fourier, por lo que realmente no hace la diferencia).

La persona con los puntajes más bajos gana. Si hay un empate, gana el programa más corto en bytes.

Generosidad

Esta recompensa de 500 repeticiones es para una nueva respuesta que juega golf con cualquiera de las funciones de Fourier. Eso incluye variables, bucles y sentencias if, etc. Esta nueva respuesta no será aceptada.

Tabla de clasificación

Consulte la sección de formato anterior:

var QUESTION_ID=55384;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),e.has_more?getAnswers():process()}})}function shouldHaveHeading(e){var a=!1,r=e.body_markdown.split("\n");try{a|=/^#/.test(e.body_markdown),a|=["-","="].indexOf(r[1][0])>-1,a&=LANGUAGE_REG.test(e.body_markdown)}catch(n){}return a}function shouldHaveScore(e){var a=!1;try{a|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(r){}return a}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading),answers.sort(function(e,a){var r=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0],n=+(a.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0];return r-n});var e={},a=1,r=null,n=1;answers.forEach(function(s){var t=s.body_markdown.split("\n")[0],o=jQuery("#answer-template").html(),l=(t.match(NUMBER_REG)[0],(t.match(SIZE_REG)||[0])[0]),c=t.match(LANGUAGE_REG)[1],i=getAuthorName(s);l!=r&&(n=a),r=l,++a,o=o.replace("{{PLACE}}",n+".").replace("{{NAME}}",i).replace("{{LANGUAGE}}",c).replace("{{SIZE}}",l).replace("{{LINK}}",s.share_link),o=jQuery(o),jQuery("#answers").append(o),e[c]=e[c]||{lang:c,user:i,size:l,link:s.share_link}});var s=[];for(var t in e)e.hasOwnProperty(t)&&s.push(e[t]);s.sort(function(e,a){return e.lang>a.lang?1:e.lang<a.lang?-1:0});for(var o=0;o<s.length;++o){var l=jQuery("#language-template").html(),t=s[o];l=l.replace("{{LANGUAGE}}",t.lang).replace("{{NAME}}",t.user).replace("{{SIZE}}",t.size).replace("{{LINK}}",t.link),l=jQuery(l),jQuery("#languages").append(l)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:&lt;(?:s&gt;[^&]*&lt;\/s&gt;|[^&]+&gt;)[^\d&]*)*$)/,NUMBER_REG=/\d+/,LANGUAGE_REG=/^#*\s*([^,]+)/;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}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="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> <tbody id="languages"> </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>

Decaimiento Beta
fuente
66
No creo que tener que generar todas las soluciones óptimas sea muy justo / interesante. Se descarta todas las implementaciones, excepto la fuerza bruta ...
orlp
55
El verdadero problema con tener que dar salida a todas las soluciones óptimas es que para una entrada larga, habrá soluciones más óptimas que átomos en el universo.
isaacg
1
@orlp Editado dando salida a todas las soluciones óptimas
Decaimiento Beta
1
¿Debería ser solo ASCII imprimible, o cualquier tipo de ASCII? ¿Y solo ASCII de 7 bits o bytes completos?
orlp
1
¿El acumulador comienza en 0?
ASCIIThenANSI

Respuestas:

9

Python, 14307118 bytes

601216 para Hamlet + 13705902 para Génesis = 14307118

Definitivamente, hay algunos senarios bajo los cuales esta solución no es óptima, como por ejemplo 1111, donde se generará 1111oen lugar de 11oo. Sin embargo, creo que es casi óptimo.

Editar: guardado algunos bytes mejorando 0o0oa 0oo.

El nombre del archivo que contiene la entrada se recibe en STDIN y se envía a STDOUT.

Resultados verificados con el intérprete oficial.

def opt_str(char, acc):
    opts = []
    char_num = ord(char)
    opts.append(str(char_num))
    if 0 < char_num - acc < 10:
        opts.append('+' + str(char_num - acc))
    if 0 < acc - char_num < 10:
        opts.append('-' + str(acc - char_num))
    if char_num - acc == 1:
        opts.append('^')
    if acc - char_num == 1:
        opts.append('v')
    if acc == char_num:
        opts.append('')
    if acc and char_num % acc == 0:
        opts.append('*' + str(char_num//acc))
    try:
        if acc // (acc // char_num) == char_num:
            opts.append('/' + str(acc // char_num))
    except:
        pass
    return [opt for opt in opts if len(opt) == len(min(opts, key=len))]

acc = 0
result = []
pos = 0
with open(input(), "r") as myfile:
        in_str = myfile.read()
while pos < len(in_str):
    i = in_str[pos]
    pos += 1
    if i in '0123456789':
        if i != '0':
            while pos < len(in_str) and in_str[pos] in '0123456789':
                i += in_str[pos]
                pos += 1
        if i == str(acc):
            result.append('o')
        else:
            result.append(i + 'o')
        acc = int(i)
    else:
        opts = opt_str(i, acc)
        result.append(opts[0] + 'a')
        acc = ord(i)
print(''.join(result))
isaacg
fuente
@Shebang Bueno, estoy bastante seguro de que el resultado de Geobit es incorrecto, vea mis comentarios allí.
isaacg
Había muy poco, pero ganaste con solo 5 personajes (tú y Razvan empataron, así que usé la longitud de tu código como desempate)
Beta Decay
2
@BetaDecay Nunca antes había visto que el desempate fuera relevante entre un par de programas sin golf.
isaacg
Sí ... yo tampoco: P
Beta Decay
13

> <>, 14310665 bytes

601398 para aldea + 13709267 para génesis

Esto todavía es un trabajo en progreso y lleva mucho tiempo completarlo.

v
0
>i:0(?;:r-:?!v:0a-)?v     v
  >~:v       ~      >:a(?v>
 :1+?v~'v'o  v      o'^'~\:0)?v
     >n      vno'+'      ^?=1:<
^        o'a'<
Aaron
fuente
Eso es una locura, lástima que no sea óptimo.
orlp
Estoy trabajando en usar /, * yo, pero está empezando a ocupar un lugar más.
Aaron
18
Está
Bueno, esta es una brillante elección de idioma: D
Decaimiento Beta
Su programa no se ajustaba a los criterios para la recompensa (ninguna de las respuestas publicadas sí), por lo que se lo he otorgado porque me encanta que haya usado <> <.
Beta Decay
8

Java, 14307140 bytes

Hamlet - 601,218

Génesis - 13,705,922

La idea aquí es hacer todo el trabajo por adelantado, haciendo un mapa de caracteres-> caracteres. Luego puedes recorrer y tomar las cuerdas más cortas.

Se debe hacer una pequeña excepción para los números, así que los reviso en el bucle principal. Sin embargo, sigue siendo rápido y maneja el caso de prueba más grande en unos segundos. Es posible que pueda modificar esta sección por un par de bytes más, pero estoy bastante seguro de que está cerca de lo óptimo.

La entrada es un nombre de archivo como argumento. La salida se escribe en un archivo inputFilename_out.4y el recuento de caracteres se envía a STDOUT.

Esto es 1737 bytes para el desempate, completamente sin golf. Puedo jugar mucho golf si es necesario, pero seguirá siendo un poco grande.

import java.nio.file.Files;
import java.nio.file.OpenOption;
import java.nio.file.Paths;
import java.text.NumberFormat;

public class FourierMapper {
    public static void main(String[] args) throws Exception {
        FourierMapper fm = new FourierMapper();
        fm.createMap();
        String filename = args.length>0? args[0]:"bible.txt";
        String out = fm.fourierize(filename);
        System.out.println(out.length());
        Files.write(Paths.get(filename + "_out.4"), out.getBytes(), new OpenOption[]{});
    }

    String[][] map = new String[9999][256];
    void createMap(){
        for(int from=0;from<9999;from++){
            for(int to=0;to<256;to++){
                if(to<10||from<1){
                    map[from][to] = ""+to;
                } else if(to==from){
                    map[from][to] = "";
                } else if(to-from==1){
                    map[from][to] = "^";
                } else if(to-from==-1){
                    map[from][to] = "v";
                } else if(to>99){               
                    if(to%from<1){
                        map[from][to] = "*"+(to/from);
                    } else if(to>from&&to-from<10){
                        map[from][to] = "+"+(to-from);
                    } else if(from>to&&from-to<10){
                        map[from][to] = "-"+(from-to);
                    } else {
                        map[from][to] = ""+to;
                    }
                } else {
                    map[from][to] = ""+to;
                }
            }
        }
    }

    String fourierize(String filename) throws Exception{
        StringBuilder out = new StringBuilder();
        byte[] in = Files.readAllBytes(Paths.get(filename));
        String whole = new String(in);
        out.append(in[0] + "a");
        int number = -1;
        for(int i=1;i<in.length;){
            if(in[i]<58&&in[i]>47){
                number = in[i]==48?0:((Number)NumberFormat.getInstance().parse(whole.substring(i,i+4))).intValue();
                out.append(""+number+"o");
                i += (""+number).length();
            } else {
                if(number<0)
                    out.append(map[in[i-1]][in[i]]+"a");
                else
                    out.append(map[number][in[i]]+"a");
                number = -1;
                i++;
            }
        }
        return out.toString();
    }

}
Geobits
fuente
Creo que esto no maneja cadenas de dígitos con ceros a la derecha correctamente. Por ejemplo, en la entrada 01, creo que sale 01o, lo cual no es correcto.
isaacg
Además, creo que estás haciendo mal uso del acumulador. En la elsecláusula del bucle principal, usted elige entre usar el valor real del acumulador y el valor del carácter del carácter anterior. No puede hacer la última elección si las dos son diferentes, porque eso significa que utilizó oel tiempo anterior, y el acumulador no contiene el valor del personaje anterior.
isaacg
Bien, ambos deberían arreglarse ahora. ¡Gracias!
Geobits
Cuando ejecuto esto en mi máquina, obtengo 625474 para Hamlet y 13705922 para Genesis.
isaacg
@isaacg ¿Lo está ejecutando en el mismo archivo (con las mismas terminaciones de línea)? Me encontré con un problema con las terminaciones de línea anteriormente. Cuando ejecuto el mío y el tuyo en el mismo archivo, ambos muestran las puntuaciones publicadas.
Geobits
2

PHP, 14307118 bytes

601,216 (Hamlet) + 13,705,902 (Biblia)

function f($file) {
    $text = file_get_contents($file);

    $a = 0;

    for ($i = 0; $i < strlen($text); $i++) {
        $chr = $text[$i];

        if (ctype_digit($chr)) {
            while ($chr && isset($text[$i + 1]) && ctype_digit($text[$i + 1])) {
                $chr .= $text[$i + 1];
                $i++;
            }

            if ($a == (int)$chr) {
                print "o";
            }
            else {
                $a = (int)$chr;
                print $chr . "o";
            }

            continue;
        }

        $ord = ord($chr);

        $mapping = array(
            '' => $a,
            '^' => $a + 1,
            'v' => $a - 1
        );

        for ($j = 2; $j <= 9; $j++) {
            $mapping["+$j"] = $a + $j;
            $mapping["-$j"] = $a - $j;
            $mapping["*$j"] = $a * $j;
            $mapping["/$j"] = $a / $j;
        }

        foreach ($mapping as $op => $value) {
            if ($value === $ord) {
                $a = $value;
                print $op . "a";
                continue 2;
            }
            else if ($value . '' === $chr) {
                $a = $value;
                print $op . "o";
                continue 2;
            }
        }

        $a = $ord;
        print $ord . "a";
    }
}

Salida de Fourier para Hamlet

Funciona de la siguiente manera:

  1. Itera sobre cada carácter en la entrada;
  2. Si hay una secuencia de dígitos iniciales que no son 0, establecerá el acumulador en ese número y lo generará como número. También verifica dígitos similares;
  3. De lo contrario, verifica si hay una forma más corta de generar el carácter actual (en lugar del código ASCII + símbolo "a" = 4 caracteres) realizando una operación básica (+ - * /) en el acumulador con un número entre 2 y 9; obviamente, también trata de comparar / incrementar / disminuir;
Razvan
fuente