24
\$\begingroup\$

Challenge

Given a string as input, golf down the Fourier program which outputs that string.

In Fourier there is no easy way to output a string: you have to go through each character code and output that as a character.

Fourier

The language is based upon an accumulator, a global variable which is initialised to 0 at the start of the program. This is used by almost every operator in the language. Only some do not change the value of the accumulator.

Character out

a

Takes the value of the accumulator as the ASCII code and outputs the character. Does not change the value of the accumulator.

If the accumulator is greater than 255, the program will return an error. Likewise if the accumulator is less than 0.

Number out

o

Outputs the value of the accumulator. Does not change the value of the accumulator.

Increase

^

Increase the accumulator by one.

Decrease

v

Decrease the accumulator by one.

Add

+x

Sets the accumulator to the value of the accumulator plus the value of x.

Subtract

-x

Sets the accumulator to the value of the accumulator minus the value of x.

Multiply

*x

Sets the accumulator to the value of the accumulator multiplied by the value of x.

Divide

/x

Sets the accumulator to the value of the accumulator divided by the value of x. (Note that this is integer division, so 1/6 results in 0)

Number

n

Set the accumulator to the integer n.

Note

Here, x and n can be any integer from 0 to 2^32-1 inclusive.

More information

You must only use the operators described above. Therefore your outputted Fourier program is invalid if it uses any of the following (note that the following operators are allowed for the bounty):

  • Repeat loops
  • If statements
  • Variables
  • Random
  • Modulo
  • User Input
  • Greater/Less than operators
  • Equality operators
  • Clear screen
  • Time delay
  • Date functions

Your program can either be a full program or a function, taking in input via STDIN, a file or function arguments. You may also take input straight from the Internet.

Note that if there is a vv in your code, you should replace it with -2. The same goes for ^^, replacing it with +2.

Examples

If the input is 7n, then the expected program is:

55a110a

But you can save one byte with

55a*2a

Another way is

7o110a

Using number out.


Similarly if the input is Hello, then the expected program is:

72a101a108a108a111a

You can golf it down by 3 bytes (because outputting doesn't change the accumulator):

72a101a108aa111a

But wait, we can use the addition operator, saving 2 bytes:

72a101a+7aa+3a

Formatting

Because I'll be using Martin Büttner's Stack Snippet leaderboard, please could you format the title like so:

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

Then, you can put anything you wish below the title.

Winning

You should post the length of Fourier programs (produced by your code) to output this text file and this text file. Your score is the combined length of both Fourier programs in bytes (non-ASCII characters aren't used in Fourier so it doesn't really make a difference).

The person with the lowest scores wins. If there is a tie, the shortest program in bytes wins.

Bounty

This 500 rep bounty is for a new answer which golfs the strings using any of Fourier's functions. That includes variables, loops and if statements etc. This new answer will not be accepted.

Leaderboard

Refer to formatting section above:

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>

\$\endgroup\$
  • 6
    \$\begingroup\$ I don't think having to output all optimal solutions is very fair/interesting. It rules out all implementations except brute force... \$\endgroup\$ – orlp Aug 27 '15 at 15:19
  • 5
    \$\begingroup\$ The real problem with having to output all optimal solutions is that for a long input, there will be more optimal solutions then there are atoms in the universe. \$\endgroup\$ – isaacg Aug 27 '15 at 15:27
  • 1
    \$\begingroup\$ @orlp Edited out outputting all optimal solutions \$\endgroup\$ – Beta Decay Aug 27 '15 at 16:50
  • 1
    \$\begingroup\$ Should it only be printable ASCII, or any sort of ASCII? And only 7-bit ASCII, or full bytes? \$\endgroup\$ – orlp Aug 27 '15 at 16:55
  • 1
    \$\begingroup\$ Does the accumulator start at 0? \$\endgroup\$ – ASCIIThenANSI Aug 27 '15 at 17:33
9
\$\begingroup\$

Python, 14307118 bytes

601216 for Hamlet + 13705902 for Genesis = 14307118

There are definitely some senarios under which this solution is not optimal, such as for 1111, where it will output 1111o as opposed to 11oo. However, I think it is nearly optimal.

Edit: Saved a few bytes by improving 0o0o to 0oo.

The name of the file containing the input is received on STDIN, output to STDOUT.

Results verified with the official interpreter.

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))
\$\endgroup\$
  • \$\begingroup\$ @Shebang Well, I'm pretty sure Geobit's result is wrong, see my comments there. \$\endgroup\$ – isaacg Aug 27 '15 at 18:38
  • \$\begingroup\$ There was very little in it, but you won by a mere 5 characters (you and Razvan tied so I used your code length as the tiebreaker) \$\endgroup\$ – Beta Decay Sep 3 '15 at 8:19
  • 2
    \$\begingroup\$ @BetaDecay I've never seen the length tiebreaker be relevant between a pair of ungolfed programs before. \$\endgroup\$ – isaacg Sep 3 '15 at 8:20
  • \$\begingroup\$ Yeah... Me neither :P \$\endgroup\$ – Beta Decay Sep 3 '15 at 8:21
13
+500
\$\begingroup\$

><>, 14310665 bytes

601398 for hamlet + 13709267 for genesis

This is still a work in progress and takes a lot of time to complete.

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'<
\$\endgroup\$
  • \$\begingroup\$ That's crazy small, shame it's not optimal though. \$\endgroup\$ – orlp Aug 27 '15 at 19:42
  • \$\begingroup\$ I'm working on using /, * and o, but it's starting to take some more place. \$\endgroup\$ – Aaron Aug 27 '15 at 19:45
  • 18
    \$\begingroup\$ That's okay, fish normally grow with each telling of the story ;) \$\endgroup\$ – Geobits Aug 27 '15 at 19:46
  • \$\begingroup\$ Well, this is a brilliant choice of language :D \$\endgroup\$ – Beta Decay Aug 27 '15 at 20:02
  • \$\begingroup\$ Your program didn't fit the criteria for the bounty (none of the posted answers did), so I have awarded this to you because I love that you used <><. \$\endgroup\$ – Beta Decay Aug 18 '16 at 8:55
8
\$\begingroup\$

Java, 14307140 bytes

Hamlet - 601,218

Genesis - 13,705,922

The idea here is to do all the work upfront, by making a character->character map. Then you can just loop through and grab the shortest strings.

A bit of an exception has to be made for numerals, so I check for them in the main loop. It's still fast, though, and handles the larger test case in a few seconds. I may be able to tweak this section for a couple more bytes, but I'm fairly sure it's close to optimum.

Input is a filename as argument. Output is written to a file inputFilename_out.4, and the character count is sent to STDOUT.

This is 1737 bytes for the tiebreaker, completely ungolfed. I can golf it a lot if needed, but it's still going to be a bit big.

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();
    }

}
\$\endgroup\$
  • \$\begingroup\$ I think this doesn't handle strings of digits with leading zeroes correctly. For instance, on the input 01, I believe it outputs 01o, which is not correct. \$\endgroup\$ – isaacg Aug 27 '15 at 18:29
  • \$\begingroup\$ Also, I think you're misusing the accumulator. In the else clause of the main loop, you choose between using the actual value of the accumulator and the character value of the previous character. You cannot make the latter choice if the two are different, because that means you used o the time before, and the accumulator does not contain the previous character's value. \$\endgroup\$ – isaacg Aug 27 '15 at 18:37
  • \$\begingroup\$ Right, both should be fixed now. Thanks! \$\endgroup\$ – Geobits Aug 27 '15 at 18:54
  • \$\begingroup\$ When I run this on my machinge, I get 625474 for Hamlet and 13705922 for Genesis. \$\endgroup\$ – isaacg Aug 27 '15 at 19:25
  • \$\begingroup\$ @isaacg Are you running it on the same file (with same line endings)? I ran into a problem with line endings earlier. When I run mine and yours on the same file, they both show the posted scores. \$\endgroup\$ – Geobits Aug 27 '15 at 19:30
2
\$\begingroup\$

PHP, 14307118 bytes

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

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";
    }
}

Fourier output for Hamlet

It works as follows:

  1. Iterates over each character in the input;
  2. If there is a sequence of non 0 leading digits it will set the accumulator to that number and output it as number. It also checks for similar digits;
  3. Otherwise, checks if there is shorter way of outputting the current character (rather than the ASCII code + "a" symbol = 4 characters) by performing a basic operation (+-*/) on the accumulator with a number between 2 and 9; obviously, it also tries to compare/increment/decrement;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.