Hacker News Reader

Comment by ggerganov | Hacker News Reader

Tangentially related to quines - some time ago I was wondering if a certain program can be modified so that it prints its diff with it's previous version. If possible, you can keep modifying the program this way many times. At the end, you can reconstruct the entire history of modifications by running the program and applying the diffs iteratively.

I pondered a bit on this and thought it's impossible, but still, I made this repo as a challenge:

https://github.com/ggerganov/diff-challenge

Amazingly, someone managed recently to propose a solution for the first step [0]. Not sure if a next step is possible though..

[0] https://github.com/ggerganov/diff-challenge/commit/e4d210c16...

View on HN

The next step is basically a quine with a template of diff cruft around it. It has to output this, where N is the number of lines in the program:

  1,Nc1,3
  < HERE IT REPRODUCES
  < ITS OWN N-LINE IMAGE
  < ...
  ---
  > #!/bin/sh
  > head -n2 $0 | diff - /dev/null
  > exit 0

Since "quining" via $0 is evidently fair game, that simplifies things a lot. Here you go:

  #!/bin/sh
  sed -e 's/^X//' <<!
  X1,9c1,3
  $(sed -e s'/^/< /' $0)
  X---
  X> #!/bin/sh
  X> head -n2 \$0 | diff - /dev/null
  X> exit 0
  !

On first try, I didn't escape the dollar sigil on $0, so that got expanded to ./x3.sh, resulting in a minor difference. But since we are not doing any true quining, all I had to do was add the backslash without having to rack my brain on how to compensate for that character elsewhere; the "reproduce self accurately" requirement is trivially taken care of with $0.

With the above template, you can diff back to any body of text, so it can be easily continued.

Awesome! Thanks for showing me this approach.

Having $0 available does seem to help a lot to solve the challenge.

Replying to some old comment of mine to demonstrate hnreplies [0] functionality

[0] https://news.ycombinator.com/item?id=30014298

I think this is what you're trying to do:

Y = (X + information) + X diff Y (This is kind of golden ratio-ish, imo)

It seems to be self referential which doesn't make it impossible, just maybe impossible.

I think the trick here would be calculating the lower bound of a massive block of text that could be encoded somehow to produce a sort of hash collision.

The program would essentially just read from a big chunk of text, and reconstruct the actual source code.

You'd have a separate program to read the previous text, read your program, and find a collision in your encoding scheme that satisfied your changes and also diffed correctly.

What that encoding algorithm is, I don't know, and I'm not sure it can exist. But if it does, I think you'd have to have to have a pretty big chunk of data to collide to even write a hello world program.

This is a pretty interesting problem, but I bet it can be reduced to a simpler computability/information theory deal. I'll be thinking about this all day.

I suppose it would be posssible with a lisp.

Reply on news.ycombinator.com