Exercises
Here there should be some exercises such as programming projects, math
problems or quizes for those wishing to pursue [1]LRS in any way.
Programming Challenges
See also [2]needed projects.
This place is for suggesting programming projects that will in first place
serve practicing [3]programming, but they'll be formulated so that they
can theoretically be expanded to something useful in the end. The projects
will be roughly sorted from easiest to hardest into different difficulty
levels and within each level also at least approximately from easiest to
hardest. You can use this to practice what you've learned in [4]C
tutorial. Be sure to follow the [5]LRS principles. We more or less assume
you'll be programming in [6]C -- that's how we judge the difficulty etc.
-- but of course no one is stopping you from using another language, just
remember it may become much more easy or difficult or just awkward.
LRS programming challenge! If you desire "motivation", feel free to treat
this as a [7]game, the projects will be achievements for you to collect.
Then it would be cool if you make a [8]git repo or something to show it to
the world { I'll be glad to see it, drop me a link :) ~drummyfish } Here
are the rules:
* Award yourself points like this:
* 1 point for a completed project in level 0.
* 4 points for a completed project in level 1.
* 16 points for a completed project in level 2.
* 64 points for a completed project in level 3.
* 256 points for a completed project in level 4.
* If you complete all projects in level N, you can automatically
consider all projects of all lower levels completed as well, i.e. if
you complete whole level 2, count yourself whole level 1 and 0 as
well. (Once achieved you'll keep it forever, i.e. if more projects
appear in given level later on that you won't have solved, it won't
take away your lower level points. Hopefully you get it.)
* A project is considered completed only if you REALLY complete all of
its requirements! It's not enough to say "mmm, I could do this if I
wanted" -- no, you have to REALLY DO IT for it to count. If the
requirement is to make a complete game, a buggy demo doesn't count.
Also if you just use some cheat, use 100 libraries to do everything
for you, you know you didn't really complete it :) If it's obvious
implementing something is part of the challenge (for example collision
detection in physics engine), you cannot use a library for it, you
have to do it yourself. Just be honest with yourself.
* You CANNOT award yourself partial points, i.e. if you meet 90% of
requirements for some project, you CANNOT give yourself 90% points for
it, not even one point. Complete it 100%, then get 100% points. Again,
it doesn't count to say "mmm, I could finish this if I wanted" -- no,
until you finish it it's not finished. This is part of the challenge
and insisting on it also makes you potentially make a nice, tidy
program that will increase good in the world ;)
* You may reuse your own code without it counting as third party
library, i.e. if you write 3D renderer in one project, you can use it
in writing 3D game as another project, with it counting as if you
wrote everything from scratch just for that project.
* The thumbs up parts are not mandatory, just a little extra challenge.
* Don't [9]cheat, you're only cheating yourself :)
* If there is any doubt, [10]drummyfish is the arbiter. So if you for
example don't know if your project passes, send it to drummyfish and
he will tell you.
Level 0: Trivial, Piece Of Cake
1. hello: Make a program that outputs hello.
2. counting: Make a program that outputs numbers from 1 up to 100.
3. guess a number: Make a game in which the computer secretly thinks a
number from 0 to 9 and the player guesses the number. The computer
then says if the player won and what the secret number what.
4. password generator: Make a program which when run outputs randomly
generated password (the password must be different each time you run
the program of course). The password must be at least 10 characters
long, contain at least one decimal digit and one special character.
5. rock, paper scissors: Make a game of rock paper scissors, the player
plays against the computer.
6. average: Make a program that reads two numbers (you can assume only
non-negative integers will be input) and writes out their average (it
can be rounded, even to just integer, e.g. 3 and 8 can give 5).
7. kawaii filter: Make a program that will filter input text to make it
more kawai senpai. It has to read characters from input until end is
reached (you can consider either EOF or end of line the end of input,
that's up to you), outputting each character it reads as soon as it
reads it, except for letters r/R that will be replaced with w/W. Also
when period is read, the word desu must be output before it. For
example the input "This program is really good." will produce output
"This pwogwam is weally good desu.".
8. info tool: Make a tool that will output some basic info about real
world, the computer, its operating system or the programming language
-- you have to really retrieve this info e.g. using standard library,
OS files, language's built-in functions etc. When run, it has to
output at least three of the following things: current time, current
date, operating system name and version, programming language version,
native integer size in bits, amount of computer RAM, free disk space,
CPU name and/or frequency and/or number of cores or locale info
(language, timezone, ...). (hints: see time.h, limits.h, locale.h, man
system etc.)
9. [11]ASCII art animation: Program a simple ASCII art animation that
will play in terminal -- just make a few frames of the animation in
some text editor, then make a program that will show one frame after
another. After each frame write out like 50 spaces to scroll the old
frame away from the screen, then draw the next frame. The animation
can be advanced just with a key press, i.e. you can just have a loop
that draws the frames and at the end of the loop you just wait for
user input (but thumbs up if you can figure out how to pause for some
fixed time after each frame).
10. [12]Nim: Implement the simple variant of the game Nim for two human
players -- At the beginning there will be 15 matches, players take
turn, in each turn a player can take 1, 2 or 3 matches. That who takes
the last one loses. The game has to show the number of matches as a
numeral and also as some kind of symbols, for example:
|||||||||||||||. Players have to input 1, 2 or 3 to play their turn,
on wrong input the game has to report error and ask again. At the end
winner must be shown. Thumbs up for randomly setting the initial
number of matches between 10 and 15.
Level 1: Easy, I'm Too Young To Die
1. [13]fizzbuzz: Write the classic fizzbuzz program.
2. [14]palindrome checker: Make a program that reads one line of text
from the user and checks if it's a palindrome (i.e. if it's spelled
the same forward and backwards) or not -- you can just output yes or
no. { I fucked up and had an "anagram" checker here before, I get the
two confused, thanks to a reader for correction <3 ~drummyfish }
3. number [15]encyclopedia: Make a program that writes numbers from 0 to
1000 (including both) and about each of which it writes some facts.
These facts have to include at least the number's square, square root,
sum of its decimal digits, its [16]binary representation, prime
factorization and whether the number itself is [17]prime, perfect
number and [18]Fibonacci number.
4. [19]game of life: Make a program that simulates game of life on a
finite N * N grid, with wrapping space (i.e. a cell on the very left
of the grid is considered a neighbor of the cell on the very right in
the same row, same thing with top and bottom). Make N configurable at
least as a compile time option, draw the world as [20]ASCII art to
terminal, make the user step forward by pressing some key. You can
initialize the grid values randomly, but thumbs up for allowing
setting the initial world state (e.g. reading it from a file or
something).
5. [21]anagram checker: Make a program that reads two words and checks if
they are an anagram of each other or not (i.e. one can be made from
the other just by rearranging the letters). You can just output yes or
no.
6. text adventure: Make an interactive [22]CLI text adventure that will
take an average player at least 10 minutes to finish. Part of game
mechanics must involve inventory, i.e. picking up items, carrying them
around and using them.
7. calculator: Make an interactive calculator -- it can be a purely
[23]command line program into which user types expressions and your
program evaluates them. The functionality must be at least on the
level of the most plain physical calculators, i.e. it doesn't have to
parse whole complex expressions, but it should be able to add,
subtract, multiply, divide and find square roots. Results can be
approximate, showing just 3 fractional decimal digits. Thumbs up for
more features like handling expressions with brackets, having a
variable storing last result, converting between bases and so on.
8. [24]bytebeat: Make at least three cool sounding bytebeat songs.
9. Lorem ipsum [25]markdown generator: Create a program that generates
gibberish text in markdown format that looks like normal human text.
Each time it is run, it will generate generally a different text that
consists of 3 to 5 sections, each section starts with a heading which
starts with # after which 3 to 5 words follow, then there are two
newlines and then 3 to 5 paragraphs follow; each paragraph ends with
two newlines, except for the last one in the document which only ends
with one newline. Paragraph consists of 5 to 10 sentences; each
sentence consists of 3 to 10 words, starts with capital letter (other
letters are lowercase) and ends with period. About 1 in 20 words in
paragraphs are highlighted -- highlight is either italic (the word is
between *s) or bold (the word is between **s). After period there is
space except when it's the last period in a paragraph (then there is
no space). Words are selected randomly from some set of words that you
define (have at least 10 different words). Thumbs up for also
generating lists etc.
10. Caesar cipher: Make a program that encrypts/decrypts text with the
simple cipher known as Caesar cipher, i.e. by offsetting each letter
by certain fixed number N (e.g. with N = 2 the letter A will become C,
B will become D etc.). Assume just ASCII characters on input
(encrypted output can be non-ASCII). You can just choose and hardcode
some specific N but thumbs up for allowing to set any N. You can
input/output text from/to standard input/output or files -- it's up to
you -- also you can either make one program that does both encoding
and decoding (e.g. depending on CLI flag) or make two programs, one
for each task.
11. simple website generator: All static site generators suck ass, make
your own. Make a simple markup language and a program that will turn
this markup into [26]HTML file -- this will allow you to write HTML
websites very easily. The program will read the input file on standard
input (i.e. NOT from a file, though you can optionally support this
too) and output the HTML on standard output (again, output to file is
optional), so that the program can be used like this: cat
myfile.mymarkup | ./mymarkupprocessor > mywebpage.html. The markup
language may be super simple: let's say _ and ;_ could mark the start
and end of bold text (translating to <b> and </b> respectively) , #
and ;# start and end of heading (translating to <h1> and </h1>
respectively) and so on (you can make your own tags, this is just an
example). Basically you'll be mostly just translating your tags into
HTML tags. You don't have to implement escape sequences for special
characters (i.e. it's fine if it's impossible to have let's say the #
character in your output), but thumbs up if you do. You HAVE TO output
a correct HTML, i.e. you have to output a prologue (something like
<html> <head> </head> <body> ...) and epilogue (something like </body>
</html>) and somehow deal with possible HTML special characters in the
input text: for example if the input contains <, you have to translate
it to < etc., but it is allowed to handle non-trivial cases (like
weird Unicode stuff or something) by e.g. just replacing problematic
input with ???. [27]Unicode doesn't have to be supported on output,
you can output plain [28]ASCII. You have to support at least normal
text, 2 levels of headings and bold text, thumbs up for additional
things like images, links, lists etc. Thumbs up for additional
features like allowing to set website title with a CLI flag, choose
from several hardcoded [29]CSS styles or adding extra output formats
like [30]Markdown, LaTeX and so on. Test that you generate correct
HTML with some HTML validator.
12. filetype guesser: Create a program that reads a file and guesses its
file type. You can NOT use the file name, only the file content. First
look at the [31]magic number (file signature) -- check at least PDF,
JPEG, PNG, MP3, GIF and TAR. If this doesn't succeed, then see if 90%
of bytes are printable ASCII characters: if so, then guess the file to
be TXT, otherwise you may report unknown type (or optionally you can
try some extra checks if you want).
13. [32]brainfuck interpreter: Make a program that interprets brainfuck.
You may choose to read the input program either from standard input or
from a file (the file may have some hardcoded name, e.g. your program
will just look for a file named program.bf in the same directory). If
the brainfuck program is invalid or runtime error occurs in it, you
may just write out error and halt your interpreter. Thumbs up for
making the interpreter nicer, e.g. allowing to pass input file name as
a CLI argument, reporting more details about errors (e.g. its position
in source code) and so on.
Level 2: Mid, Hurt Me Plenty
1. [33]chess without AI: Make a program that allows two human players to
play chess, AI is not required. It can be just a CLI program that
draws the chessboard to terminal and reads moves by having players
type the squares. Of course the program mustn't allow illegal moves,
it must know if the game ended, who won (or if it's a draw) and so on.
Implement all rules correctly, i.e. don't forget en passant, castling
rights, stalemates and so on. Time controls are not required at all.
Thumbs up for some basic recording of games, undos, showing playable
squares or even having some kind of stupid AI (can just make random
moves).
2. 2D game: Make a complete 2D game in which you control a character,
with at least 5 levels. Genre is up to you, recommended is e.g.
platformer or top-down shooter. The game must have "real" graphics,
i.e. not just terminal ASCII art -- using a library like [34]SAF,
Allegro or [35]SDL may be a good choice. Sounds are not required but
thumbs up if you have them.
3. [36]gopher browser: Write interactive gopher browser -- it can be a
purely [37]command line browser. It has to be able to follow links and
go back at least one page. The program must include some basic help
and ability to save files to disk.
4. simple text [38]compression: Write a program that can compress and
decompress plain [39]ASCII text files using some very simple technique
like [40]run length encoding (RLE) or dictionary methods (you can even
use a fixed dictionary, e.g. have a list of common English words that
you will represent by some shorter symbols). You can assume input
characters will only have 7bit ASCII codes, so you can compress the
text also by dropping the 8th unused bit. You don't have to achieve
great compression ratio (you can even enlarge some files), but you
must pass the following test: take the program's source code, this
article's plain text and Wikipedia main page plain text, your program
must compress at least two of these to a smaller size (and of course
successfully decompress them into identical files). The program must
work as a [41]filter, i.e. it mustn't load the whole file into memory
or perform multiple passes, it has to use approximately same amount of
RAM for input of any size.
5. stupid chatbot: Make an entertaining chatbot that can react to basic
sentences like "how are you?", "are you a robot?", "tell me a joke"
and so on. It must give a human-like answer to at least 50 different
sentences. It has to deal with typos and text variability a little bit
(for example multiple spaces in a row or all caps text mustn't confuse
it). It must have a mood meter which changes depending on what the
partner says -- for example if the bot gets insulted, it gets more
angry and starts inserting profanity to responses; on the other hand
if it's happy it will insert nice smiley faces etc. The bot also has
to remember and use the name of its chat partner if that is brought
up. Test the bot by having it chat with itself.
6. [42]minesweeper: Implement the minesweeper game! It can be a purely
command line program if you manage to render it well with ASCII art
and make controls usable, but of course you can try making it GUI as
well. There must be at least three difficulty levels that differ by
board size and number of mines. First click must never land on a mine.
The game must show the time it took to complete it, thumbs up for
implementing a persistent top 3 score board that's saved to a file.
7. arbitrary size [43]rational numbers: Make a library that allows
working with arbitrary size rational numbers, i.e. represent each
number as a pair of numerator and denominator, the number will be
automatically allocating itself as much memory as it needs for storing
the two internal values. Negative numbers must be supported too. It
mustn't waste too much memory, i.e. whenever it changes, it will try
to simplify the fraction and, if possible, decrease its size and
allocate less memory. Size of the number will only be limited by
amount of RAM your program can use. Furthermore implement these
operations with the numbers: converting to/from the language's native
numbers (with rounding if necessary), comparisons (equal, greater,
greater or equal, smaller, smaller or equal), addition, subtraction,
multiplication, division and printing and/or converting the number to
string (at least decimal -- if the number has infinitely many
fractional digits, just cut the output somewhere).
8. image to [44]ASCII art: Make a program that takes an RGB bitmap image
and renders it with ASCII characters (i.e. prints it out to console).
You can support loading the image from just one file format of your
choice, possibly something simple like PPM, BMP or Farbfeld. The
program must support resizing the image and it must allow to just set
one dimension with keeping the aspect ratio. Thumbs up for extra
features like setting brightness/contrast and so on.
9. [45]pseudorandom tester: Make a command line program that will test
the quality of a pseudorandom generator by reading an input of bytes
and performing some statistical tests on them. You have to implement
at least four of the following tests: mean value of the whole
sequence, ratio of 1 and 0 bits, histogram (count of each value), chi
square test, correlation of consecutive values (how much a value
depends on the previous one), density plot (using ASCII art) of the
bytes interpreted as [X,Y] coordinates (i.e. basically a 2D
histogram), monte carlo computation of some constant such as pi (with
comparison to the perfect value), interpreting part of the data as
rows of pixels and drawing them (with ASCII art). Of course you may
implement more fancy tests. You may impose reasonable limits in your
measuring (for example you don't have to report all measures
absolutely precisely, for example we don't have to know exact counts
of 1 bits and 0 bits, only their approximate ratio), just make the
tool usable for its purpose. Test your program on data from
/dev/urandom (should conclude it's random) and some non-random data,
for example some txt book from Project Gutenberg.
10. educational [46]sorting visualization: Make a program for visualizing
sorting algorithms -- it may draw real graphics (either directly to
the screen or by outputting animation file) or just render ASCII art
graphics, but it has to clearly show what the sorting algorithm is
doing, i.e. which elements are being compared, which are swapped and
if it makes good sense to highlight something else (like the pivot or
already sorted part of the array), you should do it. Implement at
least bubble sort, insertion sort, selection sort and quick sort. Also
offer benchmark mode in which all algorithms race in sorting the same
array (this can be without advanced visualization, just show e.g.
number of steps for each).
11. 3D model of [47]fractal: Make a program that outputs 3D model of
either Siepinski triangle or Koch snowflake fractal. The output shall
be some simple 3D format like obj or Collada. The model can be
primitive, i.e. it can be just flat shape made of triangles which
don't have to really be connected, but the program must allow
specifying the number of iterations of the fractal (during invocation,
e.g. as a CLI flag). Check that the model is correct by opening it in
some 3D editor such as Blender.
12. [48]steganography: Make a program that hides text strings in either
pictures, sounds or another text. The program must be a nice [49]CLI
utility that performs both encoding and decoding -- it will allow the
user to specify the string to hide (this string can be simplified to
take less space, e.g. it may be converted to all caps, special
characters may be removed etc.) and the data in which to embed them.
The size of the string that can be encoded will of course be limited
by how much space there is in the data, so you can reject or shorten
the string if that's the case. The string must NOT be hidden in
metadata (i.e. exif tags, file header, after the data, ...), it must
be encoded in the useful data itself, i.e. in pixels of the picture,
samples of the sound or characters of the text, but it mustn't be
apparent that there is something hidden in the data. Use some simple
technique, for example in images and sound you can often change the
least significant bits without it being noticed, in text you can
insert typos, hyphens, replace some periods with semicolons etc. Get
creative.
13. [50]sudoku solver: Create a program to which the user somehow passes a
sudoku puzzle (in a file, through a CLI flag, interactively... the
choice is yours, but passing a new puzzle mustn't require program
recompilation) and the program attempts to solve it. It must first
employ some basic reasoning, at very least it has to repeatedly try
the elimination method, i.e. marking a set of possible values in each
empty square and then reducing these sets by crossing out values that
can't be in that square because the same value is in its
column/row/minisquare -- wherever only one value remains in the set,
it is filled in as final; this has to be repeated until no more
progress is being made. If you want, you can employ other techniques
as well. After this if the puzzle is still not solved, the program
will resort to [51]brute force which has to eventually lead to
solution (even if it would take too long). If the program finds that
the puzzle is unsolvable, it has to report it.
14. [52]football simulator: Imagine you're moving to live inawoods in a
cabin that has no TV or Internet, but it will have a simple solar
powered computer. You are a fan of football and like to watch the
matches, so you want to write yourself a program that will simulate a
game of football for you to watch. Of course it doesn't have to
compete with FIFA games, it can be pretty simplified, but it must have
some kind of true 2D graphics (not just ASCII art), done for example
with SDL, SFML, Allegro, Xlib or anything similar. It doesn't have to
be super realistic, players can be drawn even just as circles (thumbs
up for some kind of stick figures), but you must implement the basic
rules, including offside, players must have different attributes
(name, speed, accuracy etc.), they must be able to foul etc. There
must also be referees who may sometimes make a bad judgement. Of
course the program must show the score, time etc., as well as some
basic statistics (number of shots on the goal etc.). The program must
allow some flexibility and settings, for example letting 5 very
skilled players play against 10 noob players etc. -- this may be
implemented with command line flags so that you don't have to
implement a graphical menu. If you really hate football you may choose
to implement a similar game, for example ice hockey or american
football, but it really has to be comparable to this exercise, don't
make it easier for yourself.
15. language recognizer: Make a program that will be able to learn and
then recognize language of text it is given (in theory it should work
for any kind of language, be it human or computer language).
Specifically the program will first get N files, each one representing
a different language (e.g. 5 books in different human languages), then
it will take some other text and say to which of the initial N files
it is linguistically most similar. For simplicity assume only plain
ASCII files on input (you can just use some Unicode to ASCII utility
on all input files). Use some simple [53]machine learning technique
such as some variant of k-NN. It will suffice if for each training
example you construct a vector of some nice features, for example
{average word length, vowel/consonant ratio, relative frequency of
letter A, relative frequency of letter E, ...}, give each component
some weight and then just find the nearest neighbour to the tested
sample in this feature space (if you want to be more fancy, split the
input files into parts so you get more training samples, then try k-NN
with some convenient k). You shouldn't and CANNOT use neural networks,
and of course you CANNOT use any machine learning library ;) You don't
have to achieve great accuracy but your program should likely be able
to quite reliably tell e.g. German from C++.
Level 3: Hard, Ultra Violence
1. [54]quine master: Without looking it up, write a quine in one language
and radiation hardened quine in another language. Quine is a program
that outputs its own source code (don't cheat, you can't read it from
the source file), radiation hardened quine is a quine that remains a
quine if you remove any single character from the program.
2. non-trivial [55]programming language: Design language L, write its
specification and make a self hosted interpreter and/or compiler for
it, i.e. write L in L (for this you may first have to write it in
another language). L must be [56]Turing complete and you have to
provide mathematical proof of it. L must allow [57]recursive function
calls. It must not support native [58]OOP. L must be usable for
programming very basic things -- show it is so by writing [59]bubble
sort in it. Write [60]quine in it. Thumbs up for also making a
compiler.
3. 3D game: Make a complete game with 3D graphics from 1st or 3rd man
perspective that will have at least half an hour worth of gameplay
time -- the gameplay can really be 2D (e.g. like [61]wolf3D) but the
graphics must be judged as 3D by average guy who sees the game. If
your platform allows it at all, it must have basic sounds (no need for
music, but e.g. shooting should at least make beeps and so on). The
genre is up to you, it can be a shooter, platformer, RPG or anything
where you control a character. For the 3D graphics you can either use
a 3D library, in which case you HAVE TO implement textured graphics
(the textures may be [62]procedural if you want), or you can write
your own renderer. If you write custom renderer, then if it's a "true
3D", it can have just flat, untextured graphics; if it's a "[63]pseudo
3D" (like raycasting or BSP, ...), it must have at least some
texturing (e.g. walls).
4. textured 3D [64]software renderer: Make 3D software renderer that
rasterizes triangles (just like for example [65]OpenGL), with
texturing. Affine texture mapping (i.e. the easier, incorrect
texturing by linear interpolation of texturing coordinates in screen
space) will pass, but thumbs up for perspective correct texture
mapping. Implement some basic [66]shading like, e.g. Goraud with
ambient and diffuse light. You have to handle visibility even of
non-convex shapes, e.g. with z-buffer or at least approximately by
sorting triangles. It's enough if you can display some textured model
with setting camera position and rotation somehow. You don't have to
handle any 3D formats, 3D models can just be passed as arrays of
numbers (same with textures). It is enough if you output static images
e.g. to a file, but thumbs up for being able to handle real-time
rendering, animation and having extra features like transparency,
scene graph and so on. Extra thumbs up for not using [67]float.
5. [68]regular expression library: Make a library for working with
regular expressions. Implement at least the following operations:
search of regular expression, substitution of regular expressions WITH
capture groups and generating random strings by regular expression.
6. [69]chess [70]AI: Use any sane approach to write a chess engine of
reasonable strength. No, you can't just fork stockfish, write it from
scratch. It has to support xboard or UCI interface, the strength must
be such that in usually wins at least once in a 10 game match against
[71]smolchess, Maia 1500, GNU chess, Dreamer, ChessMaster, Stockfish
or similar engine with equivalent settings (search depth, time for
move etc.); alternatively it can pass by getting stable rating over
1600 on lichess or by beating someone with FIDE rating over 1500 in a
10 game match. You get the idea.
7. bitmap image editor: [72]GIMP is bloated! You have to save us by
writing a GUI image editor that's at least a bit more advanced than
the original MS paint. It has to be able to save and load images
(supporting just one format is enough), draw basic shapes (at least a
line, rectangle and circle), copy/paste parts of the image (with
rectangle select), resize the image as a whole (with scaling it), have
fill bucket and adjust brightness and contrast of the whole image. It
should be reasonably user friendly, i.e. upon quitting it should ask
if you want to save the work, it must have some basic help etc. Thumbs
up for extra features like filters (blur, invert, edge detect, ...),
layers and so on.
8. 64K intro: Make an impressive [73]demoscene-style 3D intro with music.
It must have duration of at least 1 minute and fit into a 64 KB
executable. It has to be good enough so that an average demoscener
would approve it as not completely laughable.
9. 3D [74]path tracer without [75]floating point: Write a path tracer
(NOT a mere [76]ray tracer) without using floating point. It can only
produce static images that may just be saved to a file in some simple
format (no need to draw real time animation to the screen). It must be
possible to position and rotate the camera arbitrarily and to set its
field of view. It has to support several shapes of objects in the
scene: at least a sphere, plane and cylinder, and it must support
transparent objects. Thumbs up for supporting polygonal models, depth
of field and loading scene description from a file.
10. [77]gopher fulltext search engine: Create a whole search engine (with
crawler, index creator, user frontend, ...) for the gopher network. It
can store its database just to flat files (no need to use SQL or
something like that). It has to allow at least very basic fulltext
search, i.e. about each gopher site you'll have to remember which
words it contains (and possibly their count), so that if the user
searched e.g. for cats dogs, you'll give him sites that contain both
of these words somewhere in their text -- offer options to search
either for sites containing all searched words or just some of them.
Besides this you can make simplifications (ignore case, don't support
Unicode, special characters etc.). Thumbs up for additional features
like creating a graphical map of the crawled gopherspace along the
way.
11. [78]Jpeg clone: Create a usable format for photo images with lossy
[79]compression, similar to [80]Jpeg, that achieves good compression
ratio and allows setting compression level, including setting
compression level 0 (when it will only apply lossless compression).
The format doesn't have to store any metadata, it's enough if it holds
a 24 bit RGB bitmap of arbitrary resolution. For compression it must
do at least following: separating the color and intensity channel and
subsampling the color channel (see e.g. [81]YCbCr), then converting
the image to frequency domain (probably with [82]discrete cosine
transformation) and quantizing the high frequencies, and then applying
at least some lossless compression (RLE or Huffman coding or
something). You can't use any libraries to do the described things
(e.g. DCT, color conversion etc.), do it all yourself. The program,
with medium compression level set, has to beat lz4 at compressing
photos at least 90% times (in theory it should win always but we'll
give you some margin if you fuck something up).
12. [83]text editor: Make a usable text editor. It can have [84]GUI,
[85]TUI or both, and must be at least as comparable in power to
traditional basic editors like Gedit, Pluma and so on. It has to be
able to edit gigantic files without taking up too much RAM which means
you have to be able to dynamically load just parts of the edited file
depending on which part is being edited (smaller files can be loaded
as a whole of course). Performance must be good, so you probably have
to use some advanced representation of the edited text, not just "one
big string". Cursor navigation must work like it does in other editors
(correctly handle cases like jumping vertically from longer line to
shorter line and back). All basic features must be present, including
save/save all/search/replace string/cut/copy/paste/showing cursor
position/etc. Additionally it must allow editing multiple files at
once (i.e. tabs, screen splits or something like that) and configuring
the editor a bit (something like show/hide line numbers, set font
size, dark mode etc.). You don't have to support other encodings than
ASCII or syntax highlighting (but thumbs up even for hardcoding some
generic syntax highlight).
13. console [86]emulator: Make an emulator of either [87]PlayStation 1,
Nintendo64, GameGear or any version of [88]GameBoy (GB, GBC or GBA).
You can use a library for 3D rendering if you need it. You don't have
to implement networking or weird/non-standard features (like light
sensor etc.). You don't have to achieve high accuracy but at least a
few games should be playable. You have to allow saving/loading game
states. Sound support can be basic.
14. [89]genetic programming: Create a [90]KISS genetic programming
framework. Make some kind of simple, low level model of computation,
its language (something like Turing machine, brainfuck, Forth etc.)
and its interpreter, then implement firstly generating random
programs, secondly randomizing (mutating) existing programs and
thirdly combining existing programs (creating offspring). Now create a
system that will spawn a population of random programs and will then
direct its evolution by generations toward optimizing performance at
some given task -- this performance will be measured by fitness
function (which will somehow score any given program depending on how
well it's working) that will be customizable in your framework, i.e.
anyone must be easily able to rewrite the fitness function to whatever
he desires (it's okay if changing fitness function requires
recompilation of your program). In each generation your framework will
remove badly performing programs, breed new programs by combining well
performing ones, randomly mutate some programs and add in a few new
completely random programs -- specific parameters of this must also be
curstomizable (again, recompilation here is okay). Test this by
evolving some simple program (solving a maze, quadratic equation,
blurring an image or something similar).
Level 4: God Tier, !Nightmare!
1. 3D [91]physics engine without [92]floating point: Warm up for the god
tier by making a 3D physics engine without using floating point,
usable in real time. It must support complex shapes, i.e. not just
plain spheres ;) The engine can use rigid body or soft body physics,
or both. It doesn't have to be physically accurate but should produce
results that an average observer will judge realistic enough for a
game.
2. [93]operating system: Make a whole [94]self hosted operating system
with your own custom kernel, with basic [95]GUI and tools such as a
text editor, file browser and programming language compiler. Throw in
some games because without them your OS will be boring. Run the OS on
real hardware. It doesn't have to support networking, sound, USB and
similar bloat, but thumbs up if you manage even that.
3. [96]MMORPG: Make both client and server for an MMORPG game. The game
has to support 3D graphics (but can also have 2D frontends) and have
some basic lore that makes sense. Remember, it is MASSIVELY
multiplayer game, so you have to be able to handle at least 1000
players connected at the same time on some kind of affordable
computer. There must be chat, PvP and PvE combat. Thumbs up for
releasing it all under [97]CC0.
4. [98]Python: Implement the Python programming language, INCLUDING its
whole standard library. Bonus points for finishing before the version
you are implementing stops being supported.
5. the grandest program of all time: Make a program that (in a simplified
way but still) simulates the whole [99]Universe and allows its user to
explore and zoom in on anything not just in vast space but mainly on
Earth, in big and small scales AND in all times in past and future,
while the simulation approximately matches our available data (i.e.
recorded historical events, famous people, geography, known bodies in
the Universe etc.) and procedurally
generates/interpolates/extrapolates unknown data (i.e. for example if
we don't know what Napoleon did on a certain day, the program will
make some guess and show him doing something). This will be the great
visual encyclopedia in which one can observe the big bang, [100]Jesus,
dinosaurs, black holes, the future destruction of Earth and so on.
6. ruin [101]bitcoin: Make a program that can mine one bitcoin by running
for at most one minute on some consumer laptop released before year
2010. Warning: this is probably unsolvable, but if you solve it you
may help save the planet :P
TODO: tetris, voice synth?, snake, quadratic equation, fractals, 2D
raycasting, fourier transform, primes, image library, web browser, diff,
HTML parser/visualizer?, markov chain, syntax beautifier, grep, some kinda
server, function plotter, pi digits, 2D physics engine, encryption?,
custom markup lang, procedural MIDI, machine translation?, maze gen.,
genetic prog., language recognizer, AI?, photogrammetry, solar system
simulator, emulator, chat (P2P?), auto integrator, steganography, driver?
...
Quiz/Questions/Problems/Test
Here are some questions to test your LRS related knowledge :D Questions
here are of varying difficulty, areas and may potentially have even
multiple solutions, just like in [102]real life.
Bear in mind the main purpose of this quiz is for you to test your
understanding of things AND possibly learn something new or spark some
curiosity -- don't rage if you get something wrong or if maybe the
question is worded badly (which can happen) or even if the answer here has
an error or something (which can also happen), the important thing is you
gain new knowledge, if only something like "oh, this is a thing" or "this
is a nice kind of problem I haven't seen before" etc.
1. What's the difference between [103]free software and [104]open source?
2. Use numbers 1, 3, 4 and 6, each exactly once, with any of the basic
arithmetic operations (addition, subtraction, multiplication,
division) and brackets to get the result 24.
3. Name at least 10 different [105]programming languages.
4. Why is text written on a piece of paper flipped horizontally when
viewed in a mirror -- why is it not flipped vertically?
5. Say we want to generate a random number from 0 to 999 (including both)
with uniform probability distribution (i.e. every number is equally
likely). In C we often do it using the modulo operator like this: int
num = rand() % 1000. However there is a problem with this -- describe
what the problem is and how its negative effect can be reduced. Hint:
it's called modulo bias.
6. Why is it better to have round manhole covers than square ones?
7. What's the difference between [106]data and [107]information?
8. Bob has written a program and then committed [108]suicide because
Alice sued him for sexual harassment. His program is now
[109]unmaintained. Bob's program uses 10 libraries. The probability
that the API of one such library will be [110]updated and changed in
any given year is 5%. If this happens, Bob's program will stop
working. During the next 5 years what is the probability of his
program breaking?
9. What will the following C (C99) snippet print out? int x = 2;
putchar('a' + ((1 == 3 > 2) + ++x));
10. Order the following software by the date of the release of their 1.0
version from oldest to newest: [111]TempleOS, [112]MS DOS, original
[113]Unix, [114]Linux, [115]Windows. Also point out which one stands
out from others and why.
11. Please manually evaluate the following expression: (log2(64) - cos(0))
* (6! + 123) / (1 / 19).
12. If you're running in a race and overtake the guy who's currently in
third place, what place will you be in?
13. When multiplying two N bit numbers (unsigned integers, direct
representation), what is the minimum number of bits we will generally
(i.e. for any possible input numbers) need to store their product?
Prove it.
14. We have two gears, each of same size and same number of teeth. Gear A
is fixed in place, it can't move or rotate, gear B runs around gear A
so that it keeps touching it (and therefore rotates along the way)
until it gets to the place where it started. How many revolutions
around its own axis (from your stationary point of view) has gear B
made?
15. The sum of penis lengths of [116]Bill Gaytes and [117]Steve Jewbs is
14 millimeters. Bill's dick is 4 millimeters longer than Steve's. What
are their penis lengths?
16. What's the worst socioeconomic system in the world? You don't even
have to say why because that would take too long.
17. Manually convert the [118]binary numeral 10110000000010110101 to
hexadecimal.
18. Why do astronauts on the ISS feel weightlessness?
19. How would you compute the circumference of a circle with radius r
without using floating point? Consider just the approximate value of
pi ~= 3.14, i.e. write the formula multiplying 2 * r by 3.14 only
using whole numbers (of course the result will be rounded to whole
number too).
20. Name at least five licenses commonly used for [119]FOSS programs, five
text editors/IDEs commonly used for programming and five operating
systems whose source code is mostly free-licensed (none of these is
allowed to be using the same or forked kernel of any other).
21. What is the minimum number of [120]bits that will allow us to
represent 12345678910111213 distinct values?
22. Give at least one example of [121]analog electronic device and one of
[122]digital mechanical device.
23. Transitive [123]relation is such that if element A is in relation with
B and B is in relation with C, then also A is in relation with C. Give
one real life example of transitive relation and one real life example
of relation that is NOT transitive.
24. Is physical violence ever justified?
25. Find a normalized (having length 1) [124]normal ([125]vector that's
perpendicular to surface) of the [126]triangle defined by vertices A =
{1,2,3}, B = {5,5,1} and C = {1,5,2}. (Orientation doesn't matter.
Geometric, not [127]sexual.)
26. Why will (in a typical programming language such as C) an infinite
[128]recursion crash the program but infinite loop generally won't?
27. Answer yes/no to following: Is base-three number 2101 greater than
base-seven number 206? Is using [129]gemini a good idea when
[130]gopher exists? Is there any [131]triangle (in Euclidean geometry)
whose one side is longer than the sum of lengths of its other two
sides?
28. There are two walls 2 meters apart, the right wall is moving left by
the speed 0.1 m/s, the left wall is moving right by the same speed 0.1
m/s. There is a fly in the middle between the walls, flying by speed 1
m/s. It is flying towards one wall, then when it reaches it it turns
around and flies towards the other wall etc. When the walls completely
close in, what distance would the fly have traveled? (There is a
simple solution.)
29. Solve these [132]anagrams: no cure sir, come piss ron, ginger, nicer
shops, fog tag, trek now.
30. At what times, with precision to seconds, do clock hands overlap (just
compute AM, PM is the same)?
31. In 3D computer [133]graphics what's the difference between
[134]shading and drawing [135]shadows?
32. Can we say that the traditional feed forward [136]neural networks are
[137]Turing complete? Explain why or why not.
33. Wicw mx uum yvfe bbt uhmtf ok?
34. 8 bit binary value 10000101 will be interpreted as number 133 under
unsigned, direct representation, but what number will it represent in
[138]two's complement representation?
35. What is the Big O time [139]complexity of worst case scenario for
[140]binary search?
36. Does the statement "10 does not equal 10" logically [141]imply that
intelligent alien life exists?
37. Consider a function f(x) = sqrt(1 - x^2) with x belonging to <-1,1>.
Convert it to [142]polar coordinates, i.e. write function g(angle)
that for given angle (in [143]radians) returns distance from origin
and specify for which values of angle the function is defined.
38. What is the principle of [144]asymmetric cryptography and why is it
called asymmetric?
39. What is the main reason for [145]Earth having seasons (summer, winter,
...)?
40. Name at least three [146]x86 [147]assembly instructions and shortly
explain what they do.
41. Point out what's highly unusual or uncommon about this paragraph. That
is find a quality of this paragraph that you wouldn't normally think
to find if you took a random paragraph from, say, a random book in
your library, or in similar work. It's not that difficult.
42. WARNING: VERY HARD. There are two integers, both greater than 1 and
smaller than 100. P knows their product, S knows their sum. They have
this conversation: P says: I don't know the numbers. S says: I know
you don't, I don't know them either. P says: now I know them. S says:
now I know them too. What are the numbers? To solve this you are
allowed to use a programming language, pen and paper etc. { Holy shit
this took me like a whole day. ~drummyfish }
43. Compare advantages and disadvantages of [148]hash tables vs binary
[149]trees for storing text strings, especially in regards to
searching the string database.
44. A [150]woman gave birth to two sons in the span of a single hour, i.e.
they are of the same age, but they aren't twins. How is this possible?
45. Name at least two TCP/IP or OSI [151]network layers: about each
shortly explain its purpose, addressing and at least one protocol of
this layer.
46. We know [152]HTTPS is shit because it's [153]encrypted and requires
[154]certificates. Explain what these certificates are, why HTTPS
needs them, how their absence could be "abused" and who issues them.
47. What's the next number in this series: 0, 1, 1, 2, 1, 2, 2, 3, 1, 2,
2, 3, 2, 3, 3, 4, 1, 2, 2, 3?
48. We have two barrels, one with water, one with wine, each having the
same amount of liquid. We take a cup, fill it with water from the
water barrel, pour it over to the wine barrel, mix it up, and then we
fill the same cup with this mixture of water and wine from this barrel
and pour it back to the water barrel. Both barrels now have the same
amount of liquid again, but the liquids are mixed. What percentage of
water is in the water barrel and what percentage of wine is in the
wine barrel? Find a general formula for a cup of any size.
49. In context of programming languages explain the difference between
[155]lvalue and [156]rvalue -- Where do they appear? What are they?
How do they differ and what conditions are placed on each? Also place
each of the following expressions under these categories (i.e. say
which are lvalues, rvalues or both; details may depend on programming
language, so just comment on that): 123, someVariable + 123,
someArray[20], *(somePointer + 4), someVariable.
50. Which star is the closest to [157]Earth?
51. A symmetric [158]relation is that for it hold that if A is in relation
with B, then also B is in relation with A (for example "is married
to"). Antisymmetric relation is that for which it holds that if A is
in relation with B and A is distinct from B, then B is NOT in relation
with A (for example "is parent of"). Give an example of relation that
is both symmetric and antisymmetric.
52. Is [159]LGBT [160]good?
53. Write a [161]C function in 60 characters or fewer that takes a string
(char *, consider zero terminated ASCII string) and replaces all
semicolons in it with colons (; -> :). It can return nothing (void).
54. Order the following [162]people by date of their birth from oldest:
[163]Alan Turing, Caesar, [164]Buddha (Siddhartha Gautama), Johannes
Gutenberg, Aristotle, [165]Charles Babbage, [166]Linus Torvalds,
[167]Jesus, [168]Adolf Hitler, Muhammad (prophet of Islam),
[169]Albert Einstein, [170]Richard Stallman, Napoleon, Leonardo da
Vinci, [171]Karl Marx.
55. Start with number 967; in each step you can either add all the digits
(e.g. 456 -> 4 + 5 + 6 = 15), multiply all the digits (e.g. 45 -> 4 *
5 -> 20) or shuffle the digits in any way (e.g. 320 -> 23); your goal
is to get to number 3. { This one is mine. ~drummyfish }
56. State at least 5 reasons for why [172]Rust sucks so much.
57. Find at least one function f(x) that's defined for all non-negative
integers and for which it holds that x + f(x) - f(x + 1) = 0. (It's
enough if you show a sequence of numbers with obvious continuation.)
58. What do we call a program that prints its own source code?
59. You receive a 1 bit (black&white) image of 8x8 resolution encoded as
hexadecimal string 0xf91919ffff98989f. The string encodes consecutive
rows of pixels from top to bottom, each pixel with 1 bit. What does
the image show?
60. Show (even just geometrically) that for EVERY right triangle if we
draw a circle going through all its vertices, the triangle's
hypotenuse (longest side) will be the circle's diameter and the
circle's center will lie in the middle of the hypotenuse.
61. What was the name of the computer that first beat the world [173]chess
champion in an official match and in which year, with tolerance
plus/minus 2, did it happen?
62. Consider the following set of numbers: 416, 81, 82, 69, 94, 28, 785,
44. Which of the following numbers belongs among them: 609, 11, 436,
88, 61 or 325?
63. As a programmer how would you represent a [174]set that may contain
integer numbers from 1 to 32 (including both)? What's the minimum
number of bits you will need for storing this set? Additionally, how
would you implement a multiset? I.e. what if you wanted to further
allow any number in the set to potentially be present more than once
(you can suppose an upper limit for this count at 255)? How many bits
will you need then? Hint: set is much different from a list, for
example order of its members doesn't matter.
64. What's heavier, 20 kilograms of black hole or 30 kilograms of nothing?
65. We have a village of 27 people; in upcoming elections 17 want to vote
for candidate A and 10 for candidate B. People will be divided into 3
districts, each with 9 people -- in each district one candidate will
be picked by majority of votes, and then the candidate who wins in
most districts will win the elections. Sort people into districts so
that candidate B wins.
66. Some rich faggot got himself a house with opening roof -- it's a flat
roof that after a button press will start to slide and so enlarge the
hole in the roof linearly from 0 to 10 m^2 over 10 seconds. Closing is
the same, just in opposite direction. Some idiot pressed the button
during rain, the roof is opening and it's raining in the house all
over his stereo and home cinema, he will close the roof but he can
only do it once it has opened completely (so it will be raining inside
for 20 seconds). The rain's intensity is such that 1 m^2 of area
catches 1 litre of water in 1 second. When the roof has closed, how
much water has poured into the room?
67. Please tell me why a human without pressure suit diving under water to
great depth will be rekt to pieces by the pressure while a small fish
made out of jello is just fine under that enormous pressure.
68. Rewrite the following snippet so that it [175]doesn't perform any
branching: if (a > 10) a += 16; else a += 4;. Watch out, you can't use
the ternary operator (a += a > 10 ? 16 : 4;) because that's typically
just a syntax sugar for a branch.
69. [176]Elon Musk's net worth is about 200 billion USD, suppose he spends
all his net worth on $1 prostitutes, how many times to the Moon and
back would they reach? Suppose the length of a [177]woman with
stretched arms is 2 meters, distance to the Moon 380000 km and neglect
the fact that there are only 8 billion people on Earth. Also
considering cost of normal living to be $30 per day and average life
span 70 years how many lifetimes could he live off of this fortune?
70. Say we have a square digital image, i.e. a grid of pixels of
resolution N x N. We want to scale it down to N/2 x N/2. For this we
could subdivide the image into 2x2 blocks and out of each block take
only one pixel, for example the top left one, discarding the three
other pixels. However there is a danger in doing this -- for example
downscaling a black and white [178]dithering pattern (a kind of
checker board) this way would result in either a completely black or
completely white image, drastically changing the overall brightness of
the whole image! What's this problem called and how could we prevent
it?
71. Give numeric answers to queries that will follow, then compute average
error against each correct answer; you want an error not greater than
3. Number of essential software freedoms defined by GNU. Year when
Creative Commons non-profit was established. PDP 10 word size divided
by 5 (use integer division). Century (its one-based sequential number)
in which Western Roman Empire officially ended (lost its last
emperor). Century in which [179]Nikola Tesla was born. Year when first
man set foot on the Moon.
72. You've probably seen a game freeze and become unresponsive and then
you likely heard audio get stuck too in a weird way: a short piece of
sound is just played over and over like a broken vinyl record. Why
does this happen? How and WHY is audio typically implemented here?
73. Mention at least one advantage and one disadvantage of using
[180]matrices to represent transformations in 3D engines.
74. A nudist is lying completely horizontally on a beach with his dick
pointed up towards the sky when a hot 16 year old jailbait walks by
and he gets an erection, the sun is shining under the angle 20 degrees
(measured from horizon), his dick is now pointed up completely
vertically and casts a shadow that reaches up to his feet, i.e. the
shadow (completely horizontal) has a length of 60 cm. How long is his
dick (with erection)?
75. If your computer resides in a private network that's connected to the
Internet through a router that performs network address translation
([181]NAT, common with many ISPs), why you typically cannot host a
server that would be publicly accessible from the outside
[182]Internet? I.e. explain how NAT works and say what's preventing
outside computers from reaching your server behind it. How can you
make your server work even behind NAT?
76. We know that in C (C99) we can kind of use arrays and pointers
"interchangeably", we are taught they are really the same. However
show at least one example of when the difference matters, i.e.
considering e.g. int *a; vs int a[N]; write some expressions with a in
it where the distinction will be significant.
77. Write sed substitution command (the one that starts with s/) that will
convert Markdown links (format: [link text](destination)) to HTML
links (format: <a href="destination">link text</a>). You probably need
[183]regular expression capture groups for this.
78. Give at least three examples of palindromic English words (written the
same forward and backwards), each at least four letters long.
79. Six extremely obese [184]women ([185]Rust developers) -- three normal
and three lesbian -- want to get to a party that's in the sixth floor
of a building. As they are morbidly obese using stairs is not an
option, they have to take the lift. The lift is on the ground floor
but its outside button is broken, it can only ride if there is at
least one human inside it who controls it (and it also doesn't go to
any other floor than the two), but it also cannot carry more than two
women at once (remember, they are obese). Lesbian must never outnumber
the normal women otherwise they wouldn't be able to control themselves
and would rape them. The women are too dumb to solve the problem of
how to get to the sixth floor without any rape happening, they call
you to help them -- find a solution to this.
80. Does 0.999... (infinitely many 9s) equal 1?
81. If [186]capitalism is bad why are people migrating into capitalist
countries such as [187]USA?
82. Why are low quality videos "blocky"?
83. What's the next number in the following sequence? 0, 1, 5, 19, 65,
211, 665, 2059, 6305, 19171, 58052, ???
84. Programming language specifications sometimes purposefully leave some
behavior undefined -- for example [188]C specification says that if
you declare a local variable (variable inside a function), its initial
value is undefined, even though the specification could have simply
said the value of such variable has to be always zero which might be
safer for programmers. Why do specifications purposefully choose to
leave some things undefined like this?
85. What does [189]GNU (Richard Stallman's project) stand for?
86. Is political correctness and censorship ever justified?
87. Firstly convert the expression x + (1 + 2) / (3 - 4) to [190]postfix
notation (also reverse Polish notation). State some major advantages
of postfix notation against infix notation. Now please state
disadvantage of postfix notation, especially that which would be
significant if we e.g. use it for expression such as
myFunc(x,y,myFunc2(z)).
88. What does the [191]demultiplexer logic circuit do? Give an example of
when it's used. How is it related to [192]multiplexer?
89. [193]Optical fiber cabels mustn't be bent too much -- one reason for
this is that the fibers inside might crack, but another reason is
related to the physics of how the light travels inside. What is this
effect of optics called and why does it limit the bend radius?
90. We know that an [194]ellipse is a set of points in 2D plane that have
constant sum of [195]distances to some two given points that are
called focal points. What if we instead consider a taxicab distance
(computed as distance alongside X axis plus distance alongside Y
axis)? Consider the constant sum of distances to always be set higher
than the taxicab distance of the two focal points. What shape will we
get? Just describe the shape and intuitively show why it looks like
that.
91. What does [196]Turing tarpit mean?
92. =fgtnmtg qlcowj jakju lm vglcnr gjv dm gocl gjv qk vcjU
93. Please solve the following inequality: sin(2 * x) / (2 - 2 * sin^2(x))
- log2(1 / 8^(-1/3)) >= 0, mathematically write exactly which values
of x will satisfy it. Don't use calculator, ok? But you can look up
goniometric formulas etc.
94. Given continuous differentiable function f(x), derive the formula for
computing the length of the curve of the function graph on interval
[x1,x2]. No need to provide 100% formal proofs, you can use intuition
as long as you get the correct formula and show it works on a few
examples. For example the length of the graph of function f(x) = x on
interval [0,1] will be sqrt(2) (holds from Pythagorean theorem).
Compute the length of curve of the graph of f(x) = sin(x) on interval
[0,2 * pi].
95. If someone murders your whole family, does he deserve death?
96. Give correct answers to at least three of the following. Full name of
an influential software engineering essay that's shortened as catb.
Name of the creator and BDFL of the Perl language. First name (by
which he was known) of a famous suckless and cat-v member who commited
suicide in 2012. Name of [197]esolang made in 1972 that's considered
to be the first esolang ever. First name that was shared by the two
most famous members of the [198]Doom development team, the engine
programmer and level designer.
97. Write a function in C, in 100 characters or fewer, that counts the
number of 1 bits in a number of unsigned int type.
98. You're programming a "pseudo 3D" game that shows a 3D view from the
player's perspective but really the player only has a position and
facing direction in two dimensions, the level exists just in a 2D
plane. Enemies also have a 2D position and facing direction, and they
are rendered with 2D sprites, just like in [199]Doom or Wolfenstein
3D. Each enemy sprite has 4 versions, each for one of the four major
viewing directions: front, back and two side views (left and right).
Given player's position PP, normalized facing direction vector PD,
enemy position EP and normalized enemy facing vector ED, how do you
compute which of the four sprite versions to chose for the rendering?
I.e. from the relative positions and rotations figure out which side
of the enemy we're seeing.
99. What's the principle of [200]CPU [201]cache? How exactly does it speed
up programs? Under what conditions will the cache work well? I.e. how
should a program ideally behave to make maximum use of the cache?
100. If you answer "yes" to this question, will you have lied?
101. Form a word by answering each following sentences with one letter.
Binary number 1011 in hexadecimal. Base of natural logarithm. x =
min(max(0,t - 1),1), y = 2 - t for 1 <= t <= 2 otherwise t mod 1, t
goes from 0 to 3. Number whose square is -1. 'U' - 'T' + 'R'.
102. In C this float x = 16777216; printf("%d\n",x == (x + 1)); outputs 1
(or at least it is possible) -- what the fuck. How can a number equal
itself plus one? Explain what's going on here.
103. Can you be both pro-privacy and anti-censorship at the same time?
104. What's the error with the following reasoning? -1 = (-1)^(2/2) =
((-1)^2)^(1/2) = 1^1/2 = 1.
105. Let's have a [202]spiral that's drawn like this: we start with a
drawing hand (like e.g. that of clock) that points horizontally to
the right and has length r1; then the hand turns around a full circle
(doesn't matter in which direction), linearly increasing its length
to r2 as it goes. Find the formula for the length of this spiral
(this length will be something between the circumference of a circle
with radius r1 and circumference of a circle with radius r2).
106. Rounded to whole percents, what is the probability that you'll
correctly answer this question?
107. Ronald died and wasn't missed, he was just a capitalist. Every action
of that bitch only served to make him rich. Things he built but
always sold, patents he would always hold. As he jerked off to his
brands, dick got zipped up in his pants. Ron did one last happy
dance, had idiot death insurance. Do you know what kind of note this
stupid's grave would be bestowed?
108. Explain at least one of the following [203]chess concepts: fork, pin,
smothered mate.
109. There is a cube-shaped planet that has 8 houses (numbered 1 to 8),
each house on one of the 8 cube vertices. Each house is inhabited by
one alien (they're named A to H). Sometimes they get bored and want
to switch houses with others, so they organize a big moving day in
which some aliens switch houses (it's possible that everyone moves
elsewhere or that just some move and some stay where they are).
However they like their neighbors (aliens living in houses directly
connected by the same edge), so any time this house switching occurs,
at the end of the day everyone must have the same neighbors as
before. How many possible ways there are to assign aliens to the
houses so that they always have the same neighbors?
110. A [204]troll joins homosexual gayming stream and starts spamming
Hitler quotes by which he increases the amount of lulz by X percent.
However the gay starts crying so the stream censor quickly bans the
poor troll, dropping the lulz to the original level. By how many
percent have the lulz decreased now?
111. Did you enjoy this quiz?
Answers
1. Though legally similar (but not identical), free software is a
movement based on ethics and pursuing freedom for the software user,
open source is evil business movement that avoids talking about
ethics, it was forked from free software and is solely focused on
exploiting free software licenses for making profit.
2. 6 / (1 - 3/4)
3. [205]C, [206]C++, [207]Java, [208]JavaScrip, [209]Python, [210]Lisp,
[211]Forth, [212]Brainfuck, [213]Fortran, [214]Pascal, [215]Haskell,
[216]Prolog, [217]Smalltalk, [218]comun, ...
4. The mirror doesn't really flip the text -- what's left/right in front
of it is also left/right in it. It is you who flipped the text when
you pointed it at the mirror -- you most likely flipped it
horizontally so that's how you see it in the mirror, but you could as
well have flipped it vertically; then the text would be flipped
vertically in the mirror.
5. Modulo bias happens when the random number generator's range is
non-divisible by our desired range that we enforce with modulo
operator -- with shown approach some numbers then have higher
probability of being generated than others. For example if rand() here
return numbers from 0 to 1023, there is only one way to get 999 (999 %
1000) but two ways to get 0 (0 % 1000 and 1000 % 1000), i.e. 0 is more
likely to be generated. Common approach to reducing this effect is to
repeatedly generate numbers until we get one falling into the "fair"
range (this is not guaranteed to end so we should limit the maximum
number of attempts).
6. Round covers can't fall in round hole (if the hole radius is just a
tiny bit smaller than the cover, which is needed for the cover to
work); a square cover CAN fall down a square hole if it is rotated
certain way (try it if you can't see it).
7. The relationship is commonly described like this: information is
interpreted data. I.e. data is just a sequence of symbols, information
is the knowledge we extract from it.
8. The probability of program breaking is 1 minus probability of it not
breaking. For a program to NOT break during one year, all libraries
have to stay unchanged (probability 0.95 for each one): that's 0.95 *
0.95 * 0.95 * ... = 0.95^10. Similarly the probability of it not
breaking during 5 years is (0.95^10)^5, so the probability of the
program breaking in 5 years is around 92%.
9. e
10. Original Unix (around 1970), MS DOS (1981), Windows (1985), Linux
(1998), TempleOS (2007). Linux stands out because it's not an
operating system, it's a kernel (alternative answers are possible, for
example TempleOS is the only software here developed by a single man).
11. 80085
12. third
13. 2 * N. We can multiply the greatest values: (2^N - 1) * (2^N - 1) =
2^(2 * N) - 2^(N + 1) + 1; The greatest term 2^(2 * N) in binary is 1
with 2 * N zeros after it, subtracting (2^(N + 1) - 1) will always
definitely shorten this number by at least one bit (1000... minus
anything non-zero will shorten the number). So at most we will need 2
* N bits for the result, but we can't use fewer because for example 11
* 11 = 1001 -- in this case fewer than 2 * 2 = 4 bits wouldn't
suffice. So in general we need 2 * N bits.
14. two (try it, see coin rotation paradox)
15. Bill: 9 mm, Steve: 5 mm.
16. [219]capitalism
17. B00B5
18. It's not because of the distance from the [220]Earth, the force of
gravity is practically the same there (from the Earth's perspective
they're really not significantly far away, even the Moon still feels
Earth's gravity very strongly so that it doesn't fly away). It's
because they are orbiting the Earth, the path they are taking makes
them constantly be in a kind of free fall while also preventing them
from hitting the Earth (similarly to a comet who is kind of falling
towards the Earth but just narrowly misses it, the orbital path of ISS
is just much closer to being a circle than an ellipse). I.e. they feel
the same kind of weightlessness you will feel in an elevator that's
falling down.
19. (2 * r * 314) / 100
20. [221]GPL, LGPL, AGPL, [222]MIT, BSD, Apache, [223]CC0, unlicense,
zlib, WTFPL, ...; [224]vim, [225]emacs, [226]Acme, Geany, vi,
Notepad++, Neovim, Kate, nano, gedit, ...; [227]Debian, 9front,
[228]OpenBSD, [229]FreeDOS, [230]Haiku, [231]Minix, ReactOS,
[232]GNU/[233]Hurd, V6 [234]Unix, FreeRTOS, ...
21. The number is N such that 2^N = 12345678910111213, rounded up, that is
ceil(log2(12345678910111213)) = 54.
22. amplifier, voltmeter, analog hardware for [235]neural networks, ...;
abacus, mechanical calculators such as Curta, Turing machine made of
wood, ...
23. transitive: e.g. "is older than", "weights the same as", "is
descendant of", ... NOT transitive: e.g. "is in love with", "share at
least one interest", "is (direct) parent of", ...
24. no
25. We can use [236]cross product to find a vector perpendicular to two
vectors, so we can take e.g. vectors U = B - A = {4,3,-2} and V = C -
A = {0,3,-1}; their cross product is UxV = {3,4,12} = n (just look up
the formula for cross product). This is the normal, to normalize it
we'll first compute its length, i.e. |n| = sqrt(3^2 + 4^2 + 12^2) = 13
and then divide each component of n by this length, i.e. we finally
get n0 = {3/13,4/13,12/13}. As a check we can compute [237]dot product
of this normal with both U and V and we should get 0 in both cases
(meaning the vectors are perpendicular).
26. Infinite loop just performs jumps back to some previous program
instruction which can be repeated indefinitely, so unless there is
something inside the loop that will lead to a crash after many
repetitions, an infinite loop will just make the program run forever.
With recursion, however, every successive recursive call allocates a
new call frame on the call stack (so that the program knows where to
return from the function) which will lead to running out of stack
memory and to [238]stack overflow.
27. no, no, no
28. The walls will collide in 10 seconds during which the fly has been
constantly flying with the speed 1 m/s, so it traveled 10 meters.
29. [239]recursion, [240]compression, [241]nigger, [242]censorship,
[243]faggot, [244]network.
30. 1:5:27, 2:10:54, 3:16:21, 4:21:49, 5:27:16, 6:32:43, 7:38:10, 8:43:38,
9:49:05, 10:54:32, 12:00:00, you can compute it by making equations
for position of the hour and minute hand depending on time, setting
them equal and solving, i.e. you get something like tm / (60 * 12) =
(tm / 60) - (tm // 60) (where // is integer division and tm is time in
minutes); you will find the times are those when minute hand is at
multiples of 60 / 11 minues (5:27), i.e. there are 11 such times
around the circle and they are evenly spaced.
31. Shading is the process of computing surface color of 3D objects,
typically depending on the object's material and done by GPU programs
called [245]shaders; shading involves for example applying textures,
normal mapping and mainly lighting -- though it can make pixels
lighter and darker, e.g. depending on surface normal, it only applies
local models of light, i.e. doesn't compute true shadows cast by other
objects. On the other hand computing shadows uses some method that
works with the scene as a whole to compute true shadowing of objects
by other objects.
32. Basic answer is that we can't really talk about Turing completeness of
plain neural networks of this type, they cannot be Turing complete
because they just transform fixed length input into fixed length
output in a fixed number of steps -- a Turing complete model of
computation must be able to operate with arbitrarily large input and
output, it must be able to get stuck in an infinite loop etc. In
theory we can replace any neural network with logic circuit or even
just plain lookup table. Significance of neural networks doesn't lie
in their computational power but rather in their efficiency, i.e. a
relatively small and simple neural network may replace what would
otherwise be an enormously large and complicated circuit.
33. two (or txq); The cipher offsets each letter by its position.
34. The number will be negative because the highest (leftmost) bit is 1;
to convert a negative number to positive (and vice versa) in two's
complement we flip all bits and add 1, i.e. 10000101 -> 01111010 + 1
-> 01111011 which is 123; the original value therefore represents
-123.
35. log2(n); Binary search works by splitting the data in half, then
moving inside the half which contains the searched item, recursively
splitting that one in half again and so on -- for this the algorithm
will perform at worst as many steps as how many times we can divide
the data in halves which is what base 2 logarithm tells us.
36. Yes, a false statement implies anything.
37. The function plot is a half circle, so expression in polar coordinates
is quite simple: g(alpha) = 1, alpha belongs to interval <0, pi>.
38. The main difference against symmetric cryptography is we have two keys
instead of one, one (private) for encrypting and one (public) for
decrypting -- neither key can be used for the other task. Therefore
encryption and decryption processes differ greatly (while in symmetric
cryptography it's essentially the same, using the same key, just in
reversed way), the problem looks different in one direction that the
other, hence it is called asymmetric.
39. It's not the distance from the Sun (the distance doesn't change that
much and it also wouldn't explain why opposite hemispheres have
opposite seasons) but the tilted Earth axis -- the tilt changes the
maximum height to which the Sun rises above any specific spot and so
the angle under which it shines on the that spot; the [246]cosine of
this angle says how much energy the place gets from the Sun (similarly
to how we use cosine to determine how much light is reflected off of a
surface in [247]shaders).
40. For example: MOV (moves values between memory locations or registers),
JNE (jump if not equal, jumps to another instruction if comparison
resulted in non-equality), ADD (adds values in memory or registers),
CMP (compares two values and sets the flags register), RET (returns
from procedure, pops return address and jumps there) etc.
41. There is no letter "e", one of the most common letters in English and
other languages -- this is very unlikely to happen by chance.
42. 4 and 13, solution: make a table, columns are first integer, rows are
second (remember, both P and S can be making their own table like this
too). Cross out whole bottom triangle (symmetric values). P doesn't
know the numbers, so cross out all combinations of two primes (he
would know such numbers as they have only a unique product). S knew P
didn't know the numbers, so the sum also mustn't be a sum of two
primes (if the sum could be written as a prime plus prime, S couldn't
have known that P didn't know the numbers, the numbers may have been
those two primes and P would have known them). This means you can
cross out all such numbers -- these are all bottom-left-to-top-right
diagonals that go through at least one already crossed out number
(combination of primes), as these diagonal have constant sum. Now P
has a table like this with relatively few numbers left -- if he now
leaves in only the numbers that make the product he knows, he'll very
likely be left with only one combination of numbers -- there are still
many combinations like this, but only the situation when the numbers
are set to be 4 and 13 allows S to also deduce the numbers after P
declares he knows the numbers -- this is because S knows the
combination lies on one specific constant-sum diagonal and 4-13 lie on
the only diagonal that in this situation has a unique product within
the reduced table. So with some other combinations P could deduce the
numbers too, but only with 4-13 S can finally say he knows them too.
43. Hash table will only allow efficient searching of exact matches while
binary tree will also allow efficient searching e.g. for all strings
starting with some prefix. On the other hand hash table may be faster,
in ideal case searching for the match in constant time, but this will
depend on the quality of implementation (hash function, number of hash
bits, ...), in worst case hash table can degenerate to a mere list.
Binary trees will generally be a bit slower, with logarithmic time,
but here we'll also have to ensure good implementation, especially
balancing the tree -- badly implemented tree may also degenerate to a
list.
44. They are two of triplets (or quadruplets, ...).
45. For example: application layer (highest level layer, concerned with
applications communicating with each other, addressing by ports,
protocols: HTTP, Gopher, FTP, DNS, SSH, ...), transport layer (middle
level layer, concerned with delivering data over a potentially
unreliable channel, implements establishment of connection,
handshakes, reliable delivery, delivering in correct order etc.,
protocols: TCP, UDP, ...), network layer (below transport layer,
concerned with delivering packets over a network, implements routing,
forwarding etc., addressing by IP addresses, i.e. numerical machine
addresses, protocols: IPv4, IPv6, ...), OSI physical layer (lowest
level layer, concerned with sending bits between two directly
connected devices, works with frequencies, electronic circuits etc.,
no addressing, protocols: ethernet, USB, Bluetooth, ...), ...
46. Certificate is a file that contains the domain's public key (needed to
communicate using asymmetric cryptography) that is [248]digitally
signed by some "trusted authority", a business that declares itself to
be trusted and lets itself be paid for cryptographically confirming
that public keys belong to specific servers. Without certificates a
[249]man in the middle "attack" could be performed in which a middle
man could sneakily swap a public key that's being exchanged for his
own public key which would then allow him to listen to the unencrypted
communication.
47. 2, the series says the number of 1 bits in numbers 0, 1, 2, 3, 4, 5,
6, 7, 8, ...
48. Let's say both barrels hold 1 unit of liquid volume at the beginning,
n is the portion of one barrel we'll be pouring over (e.g. n = 4 means
1/4th of a barrel), x is water, y is wine. At beginning we have the
following in respective barrels: x and y. After first pour over we
have: x - x/n and y + x/n. After pour back we'll have: x - x/n + (y +
x/n)/(n+1) and y + x/n - (y + x/n)/(n+1). Note: the division by n + 1
is important, dividing by n would be an error (we are taking away a
part of barrel that is over its original capacity). Now we can just
simplify the expressions to see the amount of water and wine in each
barrel, i.e. we'll get: x * (1 - 1/n + 1/(n^2+n)) + y * 1/(n+1) and x
* (1/n - 1/(n^2+n)) + y * (1 - 1/(n+1)). So for example amount of
water in the first barrel is 1 - 1/n + 1/(n^2+n) which simplifies to
n/(n+1) -- that is also the exact amount of wine in the other barrel
(1 - 1/(n+1) simplifies to the same expression). So the answer is
there is n/(n+1) of the barrel's original liquid (and 1 minus that of
the other). Logically we see the purity of each barrel has to be the
same just because of the conservation laws.
49. The details may differ from language to language, but generally
lvalues and rvalues appear in assignment commands -- lvalue is any
value or expression that may appear on the left side of assignment,
rvalue is that which may appear on the right. For example in
myVariable = x + 4 the left side, myVariable, is lvalue, and the right
side, x + 4, is rvalue. From this follow the conditions on lvalues and
rvalues, i.e. rvalue must be something that returns some computed
value and lvalue must be something that identifies a place where a
value can be stored -- sometimes an expression can be both lvalue and
rvalue at the same time. Examples: 123 is rvalue, someVariable + 123
is rvalue, someArray[20] is both lvalue and rvalue, *(somePointer + 4)
is also both and someVariable is both too.
50. The Sun. Some people get tricked here, not realizing Sun is a star.
51. For example "is equal to" or empty relation (no element is in relation
with any other). For such a relation it must generally hold that any
element may only be in relation with itself.
52. hell no
53. For example: void r(char *s) { while (*s) s += (*s -= *s == ';') != 0;
};
54. Buddha (< -480), Diogenes (-404), Aristotle (-384), Caesar (-100),
Jesus (around -5), Muhammad (around 570), Gutenberg (around 1400), Da
Vinci (1452), Napoleon (1769), Babbage (1791), Marx (1818), Einstein
(1879), Hitler (1889), Turing (1912), Stallman (1953), Torvalds
(1969).
55. 967 (*) --> 378 (*) --> 168 (*) --> 48 (+) --> 12 (+) --> 3.
56. For example: it's bloated, slow, can't be compiled on good computers,
it's tranny software with toxic fascist community, it has issues with
legal freedom (trademarks), it has [250]code of censorship, it has no
specification, it's obsessed with "safety", the name is complete shit,
it is associated with [251]corporations, has some abomination of
[252]OOP, it's littered with dependencies, it's [253]capitalist
monopoly software, it's trying to displace [254]C, it is hosted on
[255]GitHub, the users are and devs idiots and so on and so forth.
57. We can rewrite the condition as f(x + 1) = f(x) + x from which it's
clear that the next number in the sequence is the previous one minus
its position (a bit similar to [256]Fibonacci sequence), so for
example this sequence will satisfy the equation: 0, 0, 1, 3, 6, 10,
15, ...
58. [257]quine
59. swastika
60. Draw any right triangle; drawing an identical triangle mirrored by the
hypotenuse clearly makes the both triangles together form a rectangle
(it can be shown generally all angles in it will always be 90 degrees)
in which the hypotenuse (that the both triangles share) is the
rectangle's diagonal. Now draw also the other diagonal of the
rectangle. If we draw a circle going through all the rectangle's
verticles (which is the same circle that goes through the original
triangle's vertices), it is clear (e.g. just by symmetries) its center
lies in the middle of the rectangle, i.e. on the intersection of the
diagonals; i.e. the circle's center lies in the middle of the
hypotenuse, which also implies the hypotenuse is the circle's diameter
(it's a straight line going through the circle's center).
61. [258]Deep Blue, 1997
62. 436; in the original group each number's digits have a total count of
closed loops equal to 2.
63. The most common and natural way is to use a [259]bit field, i.e. an
"array of bits" -- position of each bit is associated with an object
that may potentially be present in the set and the bit's value then
says if the object really is present or not. We want to be able to
store 32 numbers, so we'll need 32 bits; the lowest bit says if number
1 is present, the next one says if number 2 is present etc. So we can
really just use one 32 bit number to store this whole set.
Implementing multiset is similar, we just allocate more bits for each
potential member to indicate the count; in our case we suppose maximum
value 255 so we can use 8 bits for each member (in C we would
naturally implement this as an array of bytes), so we'll need 32 * 8 =
256 bits.
64. I don't know lol. (That's the correct answer, it shows we can't know
everything.)
65. District one: all A voters, district two and three will each have 5 B
voters and 4 A voters.
66. The area of the roof hole says the rate at which the water pours in,
we have to [260]integrate the hole area over the 20 seconds. We can
split this to two parts that we'll add: from 0 to 10 seconds the
function that says the area of the hole is simply f1(t) = t; from 10
to 20 seconds we can use a function f2(t) = 10 - t from 0 to 10
seconds. Integral of f1 is 1/2 * t^2 which at t = 10 gives us 50
litres; integral of f2 is 10 * t - 1/2 * t^2 which also gives 50
litres (it's logical -- opening and closing of the roof is symmetric,
same amount of water will fall in). So all in all there will be 100
litres of water in the room.
67. Well, it's not the pressure alone that destroys you, it's the
difference of external and internal pressure -- human has air of
atmospheric pressur in his lungs and other parts of body but the
pressure in the depth is greater and overpowers it, so you implode.
The fish is happy because it has water inside it, the pressures are in
balance.
68. something like a += 4 << ((a > 10) << 1);
69. About 1052 distances to the Moon, about 260926 lives.
70. It's called [261]aliasing, it's addressed by [262]antialiasing which
usually suppresses or removes the effect by increasing the sampling
frequency, in our case of downscaling image this would mean replacing
each of the small 2x2 blocks by an average pixel value in that block,
i.e. taking into account all four samples as opposed to just one.
71. 4, 2001, 7 (the word size is 36), 5 (year 476), 19 (year 1856), 1969.
72. Continuous audio is normally implemented with a [263]circular buffer
-- that is we have a buffer of audio samples of certain size N and
that is being played over and over, with the play head going from
start to finish and then back to start again; the program has to keep
updating this buffer regularly to fill it with new samples to play and
it has to keep ahead of the play head. Circular buffer is nice because
we don't have to shift it as a whole (which would require moving a lot
of values in memory), the only thing that is moving is the play head,
that's why it's used as opposed to e.g. a queue. When a game freezes,
it stops operating correctly and it stops updating the audio buffer,
so whatever is in it will just be played over and over in a loop.
73. Main advantage is that a matrix can hold any combination of
transformations and that applying all the transformations is then
simply performed by performing a single matrix multiplication which
additionally may be implemented with quite fast matrix multiplication
algorithms. Not only can a matrix represent for example the whole
translation+rotation+scale transformation of a single object, it can
hold any number of such transformations performed in any order so that
we can for example precompute a matrix that will perform world
transformation, camera space transformation and view space
transformations all at once! That's very fast. Disadvantages of
matrices may be that they can only hold affine transformations (i.e.
they can't represent ANY transformation whatsoever), it may also be a
bit harder to extract back the parameters of the transformation from a
matrix (though it can be done) etc. Also in case of some extreme
memory limitations matrices may take up more space than would be
strictly needed.
74. From the right triangle: dick_legth / shadow_length = tan(20 degrees)
=> dick_legth = tan(20 degrees) * shadow_length ~= 21.83 cm.
75. Behind NAT you're in a private network, computers inside it have no
public addresses (their IP addresses are in the private range and
potentially same as addresses of computers in other private networks),
only the router has a public IP address that's unique within the
Internet, i.e. from Internet's point of view there is only one device
connected -- your router. Computers behind this router are invisible,
so no one can connect to the server that's behind it. The possibility
of you having a two way communication from within this private network
with the outside Internet is enabled by the router who communicates
for you when you ask for it, i.e. when you (from inside the private
network) initiate the connection -- the router then creates the
connection for you and talks to the outside world for you (translating
your private address to its public address, hence network address
translation). But no one can initiate communication from the outside,
the router wouldn't know to whom he wants to speak. This can be solved
e.g. by port forwarding (setting some default computer to which
communication from outside will be redirected) or tunneling (keeping a
constant connection with some outside proxy server that's listening to
requests and resending them).
76. For example sizeof(a): if a is a pointer, size of pointer will be
returned whereas in case of array the size of the whole array will be
returned. Similarly e.g. &a: if a is a pointer, we'll get a pointer to
pointer (generally a different address) whereas in case of array a and
&a gives the same address -- that of the array's first element (though
the type will be different).
77. Something like s/\[\([^]]*\)\](\([^)]*\))/<a href="\2">\1<\/a>/g.
78. For example: poop, boob, civic, deed, level, rotor, madam, refer,
stats etc.
79. For example (L = lesbian, N = normal): LLLNNN *| -> NNNL |* LL ->
NNNLL *| L -> NNN |* LLL -> NNNL *| LL -> NL |* NNLL -> NNLL *| NL ->
LL |* NNNL -> LLL *| NNN -> L |* NNNLL -> LL *| NNNL -> |* NNNLLL.
80. yes (look it up)
81. For the same reason mosquitoes fly into the mosquito killer lamps --
they have microscopic brains.
82. Possibly for several reasons but the most prominent one is likely that
video codecs typically try to save space by not saving every frame of
the video as a picture but rather encode movements of small blocks
into which keyframes (static pictures saved at relatively low "FPS")
are chopped. This exploits temporal redundancy -- the fact that frames
close in time are similar to one another, i.e. that knowing one frame
we can most likely get approximate version of the next frame by
splitting the current frame into blocks and just moving them around a
bit. Of course this doesn't work perfectly and low bitrate or
nontypical scenes can make the blocks highly visible. It would be
possible to come up with similar methods that don't use blocks and may
look prettier but rectangular blocks of pixels are very easy and fast
to work with and the results look good enough, so they are usually
used. Another reason for blockiness of videos may be e.g. that the
keyframes themselves are compressed with some lossy JPEG-like
compression that makes them "blocky".
83. 175099, formula for the series is 3^n - 2^n.
84. To allow efficient implementations. By saying "we don't force you to
do this" the specification gives those who implement it a freedom to
do it in the most efficient way possible, depending on the specific
technology they have at hand. Of course this can get tricky, but
correctly choosing what to define versus what to leave undefined leads
to very efficient languages. Imagine for example an instruction manual
for making a boat: it may also leave the choice of its body shape up
to you, you will choose the best shape depending on your situation
(You want a stable boat? Fast boat? Cheap boat? Is this shape easier
to make from material you have at hand? Etc.).
85. GNU is Not Unix.
86. no
87. x 1 2 + 3 4 - / +; Advantages are for example not needing brackets at
all and simple parsing and evaluation, for example we don't have to
care about operator precedence. Disadvantages may be e.g. lower
readability; we also have to know each operator's arity because from
postfix notation it can't be deduced -- with infix notation expression
myFunc(x,y,myFunc2(z)) it is clear that myFunc takes 3 arguments and
myFunc2 takes 1, but if we convert it to postfix notation, we get x y
z myFunc2 myFunc3, from which it isn't clear how many arguments each
function takes.
88. It's a circuit that on its input takes data and output address -- a
number from 0 to N - 1 -- and that sends the data to one of N output
ports (identified by the given address). It can be imagined like a
switch that redirects an input stream to one of N output channels. Its
use may be for example to redirect input data, for example audio, to
one of several output devices, for example speakers, headphones and
audio recorders. Multiplexer is a circuit that does the opposite (i.e.
chooses input from N channels that is then sent to a single output
channel).
89. Total internal refraction -- light travelling in the fibers bounces
off of the walls of the fiber, but in order to bounce (be reflected)
when it hits the boundary it must hit it under an angle that's smaller
than so called critical angle which is calculated from the indices of
refraction of the fiber and the material outside of it. If the cable
was bent too much, light could hit the boundary under and angle close
to perpendicular and by this it would escape to the outside medium.
90. Kind of octagon but with unevenly long sides; a rectangle with
bevelled corners, i.e. two horizontal sides, two vertical sides, two
45 degree walls and two 135 degree walls. We can imagine taxicab
distance from given point like sort of a diamond, it creates 4
quadrants around the point, in each the distance increases linearly in
diagonal direction -- regions of constant distance here form 45 degree
angled squares. Boundaries between these quadrants form a cross of
infinite size. Taking two different points these two crosses will
overlap and form 9 regions (draw it): top-left, top-middle, top-right,
middle-left etc. Examining each of the regions we will find that it
either keeps the increasing direction the same (if both overlaid
directions are the same) or that some principal direction cancels out
and leave the sum increasing only in one principal direction --
basically we find that in each of those regions the sum increases
linearly in one of 8 directions separated by 45 degrees (except for
the middle region where the sum is constant). It's also clear the
heightmap has to stay continuous as both of the summed functions are
continuous. From all this we can deduce the shape basically.
91. It's a [264]Turing complete system (typically a [265]programming
language) that's however extremely hard to use for any practical
programming, i.e. it can be seen as a programming language in which it
is theoretically possible to program anything (anything programmable
in any other language) but practically it's impossible to program
anything significant because of the complicated nature of that
language. This terms is related to [266]esoteric languages.
92. [267]Earth or jvpcG. The cipher reverses the ASCII string and xors
every byte (that's not a space) with 0x02 (i.e. flips the second
lowest bit) -- don't bitch too much about this being too arbitrary,
you can notice the string is reversed by the last character being
uppercase and the first one being special char (?), then you can kind
of recognize the words as the encoded chars are close to their decoded
versions and the lengths of the words also hint on the words (for
example a question is quite likely to start with "What").
93. Let's simplify the left-hand side: sin(2 * x) / (2 - 2 * sin^2(x)) -
log2(1 / 8^(-1/3)) = 2 * sin(x) * cos(x) / (2 * (1 - sin^2(x))) -
log2(8^1/3) = 2 * sin(x) * cos(x) / (2 * cos^2(x)) - log2(2) = sin(x)
/ cos(x) - log2(2) = tg(x) - 1, so we get tg(x) >= 1. So that will
hold when pi/4 + pi * n <= x < pi/2 + pi * n, n is an integer.
94. Considering an infinitely small non-zero interval dx, and the graph
height increase over this interval dy, the distance increase (from
Pythagorean theorem) on this interval will be sqrt(dx^2 + dy^2). We
can replace dy by tan(alpha) * dx. By definition tangent of the
function's angle at a certain point is its derivative, so we can also
replace tan(alpha) by derivative of the function, f'(x). So we get
length increase sqrt(dx^2 + f'(x)^2 * dx^2) = sqrt(dx^2 * (1 +
f'(x)^2)) = dx * sqrt(1 + f'(x)^2). Now to add infinitely many values
over infinitely small intervals we use integrals, so to add all these
small length increases we can write the final formula: length(x1,x2) =
Integral(x1,x2) sqrt(1 + f'(x)^2) dx. Testing this on f(x) = x from 0
to 1 we get the expected length(0,1) = Integral(0,1) sqrt(1 + 1^2) dx
= sqrt(2). For f(x) = sin(x) from 0 to 2 * pi we get length(0,2 * pi)
= Integral(0,2 * pi) sqrt(1 + cos^2(x)) dx ~= 7.64, which seems about
right (it's a bit more than 2 * pi).
95. no
96. [268]The Cathedral And The Bazaar, Larry Wall, Uriel, INTERCAL, John
(Carmack and Romero).
97. For example: int c1(unsigned int x) { int r = x % 2; while (x) r += (x
>>= 1) % 2; return r; }.
98. Firstly realize we don't need player's facing vector PD at all (if an
enemy is showing us his back for example, no matter how we rotate
ourselves we'll only ever be able to see his back). Instead we'll need
a vector pointing from the player's position to the enemy position,
let's say V = normalize(EP - PP). Now let's observe our result will
depend on the relatinship between V and ED -- for example if the
vectors are the same (enemy is facing in the direction aligned with
the direction from player to enemy), the player will see the enemy
back. If the vectors are opposing, we'll see the enemy front. If the
vectors are 90 degrees, we'll see either left or right side. So we
just need to figure out what angle the vectors V and ED have between
then, which we can easily do with [269]dot product that tells us the
cosine of the angle -- so if we get dot product greater than cos(45
degrees), we see the back, if we get value smaller than cos(135
degrees), we see the front, otherwise we see the side. To distinguish
between left and right side we may use for example [270]cross product
to determine if one vector goes "left or right" from another vector.
99. Cache is a small memory placed between the CPU and main memory (RAM),
it is a very fast type of memory, faster than the main memory, but
it's also much smaller than main memory. The idea is that programs
typically do a lot of work in some small region of main memory, they
keep reading and writing the same (or nearby) memory cell(s) over and
over and only after a while move somewhere else. So once the program
starts a work in some memory area, the cache can load that area, let
the program do its work very quickly in the cache, and then (when the
program moves elsewhere) copy the results back from the cache to the
memory. It's similar to downloading a file from the Internet to the
disk, then editing the file locally and later on uploading it back.
However the cache will be effective only if the assumption we made
hold, i.e. if the program really mostly works in small areas of memory
and makes minimum of long jumps, so if a program wants to fully
utilize the cache, it should try to minimize these long jumps (for
example by putting related data close to each other).
100. There is no correct answering with either "yes" or "no" (this is
therefore the correct answer). The question can be reworded as: Is
"yes" the wrong answer to this question?, neither yes or no (or both
at once) work as an answer: answering "yes" leads to a contradiction
(by giving "yes" as a correct answer we'll imply it's actually the
wrong answer) and answering "no" would imply "yes" is the correct
answer (which we've proven to not work).
101. BENIS
102. [271]Floating point had decreasing precision towards higher values,
this one if already beyond the resolution of 1, so the float type
cannot represent this number plus one, adding one rounds the result
down to the same number.
103. no
104. We can't replace a^(b/c) with (a^b)^(1/c) if a is negative, that
equation doesn't generally hold.
105. { I hope this is right :D ~drummyfish } First imagine the graph of a
polar coordinate function that says the radius of a plain circle with
radius r depending on angle: the graph is just constant function
(horizontal line) with value r going from 0 to 2 * pi. Integrating
this function (from 0 to 2 * pi, here we simply multiply r by 2 * pi
as the graph is a rectangle) will give us the formula for the
circumference of circle: 2 * pi * r -- we'll take this largely on
intuition but it can be seen that this holds because we're adding
constant tiny increments of length from 0 to what we know is the
circle circumference (2 * pi * r). Now imagine similar function, just
starting at r1 and linearly increasing to r2, i.e. we just have a
linear function saying the spiral radius for current angle. Again,
we'll integrate this, this time getting (bottom rectangle plus upper
right triangle): 2 * pi * r1 + 2 * pi * (r2 - r1) / 2. Simplifying
this we get pi * (r1 + r2), which is hopefully the solution (we see
this will be between the circumferences of the smaller and larger
circles, also for r1 = r2 we again get the circumference of plain
circle etc.).
106. Lol what, TBH I don't know :D The answer is probably that the
question is shit because it's not even clear what it's asking, the
definition of probability here is not clear (is it probability of a
random "intelligent" man from the street answering it, or giving a
completely randomly generated answer to it or what?). 100% might in
some cases make sense (firstly we conclude that chance of guessing a
number from 0 to 100 is 1/101, but then knowing this will be the
answer we conclude we know it for sure, so we switch to 100% and then
making further reasonings it stays stable at this value, but this
probability assumes we make the reasoning we did, someone else could
make a different reasoning maybe leading to other consistent
answers). Haven't thought about it deeper yet though. If you know the
answer let me know.
107. Retard -- read the first letter of each sentence.
108. Fork: attacking two (or more) pieces at once (often done with knight)
so that the opponent can only save one. Pin: attacking a piece so
that if it moves away, it will reveal another piece behind it to be
taken (often pinning to king). Smothered mate: checkmate by knight in
which king can't move anywhere because he's blocked by own pieces.
109. This is counting graph [272]automorphisms. Let's say we assign alien
X to house 1; we can count how many possible allowed configurations
there are for this case and then multiply it all by 8 (for case when
X would be assigned to house 2, then 3, 4 etc.). Let's say neighbors
of X are U, V and W. There are 3 edges going from house 1, i.e. 3
possible ways for the first neighbor, U, to be placed -- again,
consider we put U in one place; we'll count the possibilities and
eventually multiply them by 3. Now we have 2 edges (2 neighbor
houses) remaining and 2 neighbors (V and W) to put there; again,
consider one case and then multiply that by 2. Now we have X and all
his neighbors in place, how many possible configurations are left
here? There is one house that's the neighbor of both U and V and
there is only one possibility of who can live there: the shared
neighbor of U and V -- there is just one option so this house's
inhabitant is determined. Same for V/W and U/W. That's already 7
houses assigned and the one last remaining has to be in the one house
left, so in fact by placing X and its neighbors we've uniquely
determined the rest of the houses, there's just one way. So in the
end we have 8 * 3 * 2 * 1 = 48 possible ways.
110. If the original level of lulz is a and lulz increase is n, then X =
100 * n / a. The decrease is then 100 * n / (a + n) = 100 * (a * X /
100) / (a + a * X / 100) = X / (1 + X / 100) = 100 * X / (100 + X).
111. yes
Other
Make your own exercises in daily life, adopt a mindset of taking small
intellectual (or even non-intellectual) challenges. Don't slip into
conformist consumerist life of comfort and ignorance that will make your
brain rot. Learn new things just for the sake of it -- make a game, learn
a new language, learn to play music, learn chemistry, paint a picture,
learn [273]chess, read a whole [274]encyclopedia, read Quran, solve
puzzles in magazines, construct a machine out of wood, collect rocks,
write a book, compose a song, multiply numbers in your head before sleep
... you get the idea. Even if you just play vidya games, at least play
some puzzle game or a strategy game, or a creative sandbox game, or invent
some self-imposed challenge and make it into a puzzle game if it's not, or
write a bot that plays the game for you, don't be just a zombie staring
into screen. It's good to make it a habit to do some small exercise every
day, such as play one game of chess with your computer every single day,
or watch one video about math etc. -- in a year or two you'll become
pretty good at a new skill just by this. WARNING: do not confuse this with
the so called "[275]self improvement" cult, you'd be retarded to join
that.
Links:
1. lrs.md
2. needed.md
3. programming.md
4. c_tutorial.md
5. lrs.md
6. c.md
7. game.md
8. git.md
9. cheating.md
10. drummyfish.md
11. ascii_art.md
12. nim.md
13. fizzbuzz.md
14. palindrome.md
15. encyclopedia.md
16. binary.md
17. prime.md
18. fibonnaci.md
19. game_of_life.md
20. ascii_art.md
21. anagram.md
22. cli.md
23. cli.md
24. bytebeat.md
25. md.md
26. html.md
27. unicode.md
28. ascii.md
29. css.md
30. md.md
31. magic_number.md
32. brainfuck.md
33. chess.md
34. saf.md
35. sdl.md
36. gopher.md
37. cli.md
38. compression.md
39. ascii.md
40. rle.md
41. filter.md
42. minesweeper.md
43. rational_number.md
44. ascii_art.md
45. pseudorandom.md
46. sorting.md
47. fractal.md
48. steganography.md
49. cli.md
50. sudoku.md
51. brute_force.md
52. football.md
53. machine_learning.md
54. quine.md
55. programming_language.md
56. turing_complete.md
57. recursion.md
58. oop.md
59. bubble_sort.md
60. quine.md
61. wolf3d.md
62. procgen.md
63. pseudo3d.md
64. sw_rendering.md
65. ogl.md
66. shading.md
67. float.md
68. regex.md
69. chess.md
70. ai.md
71. smallchesslib.md
72. gimp.md
73. demoscene.md
74. path_tracing.md
75. float.md
76. ray_tracing.md
77. gopher.md
78. jpg.md
79. compression.md
80. jpg.md
81. ycbcr.md
82. dct.md
83. text_editor.md
84. gui.md
85. tui.md
86. emulation.md
87. ps1.md
88. gameboy.md
89. genetic_programming.md
90. kiss.md
91. physics_engine.md
92. float.md
93. operating_system.md
94. self_hosting.md
95. gui.md
96. mmorpg.md
97. cc0.md
98. python.md
99. universe.md
100. jesus.md
101. bitcoin.md
102. irl.md
103. free_software.md
104. open_source.md
105. programming_language.md
106. data.md
107. information.md
108. suicide.md
109. maintenance.md
110. update_culture.md
111. temple_os.md
112. dos.md
113. unix.md
114. linux.md
115. windows.md
116. bill_gates.md
117. steve_jobs.md
118. binary.md
119. foss.md
120. bit.md
121. analog.md
122. digital.md
123. relation.md
124. normal.md
125. vector.md
126. triangle.md
127. gay.md
128. recursion.md
129. gemini.md
130. gopher.md
131. triangle.md
132. anagram.md
133. graphics.md
134. shading.md
135. shadow.md
136. neural_network.md
137. turing_complete.md
138. twos_complement.md
139. complexity.md
140. binary_search.md
141. implication.md
142. polar_coordinates.md
143. radian.md
144. asymmetric_cryptography.md
145. earth.md
146. x86.md
147. assembly.md
148. hash.md
149. tree.md
150. woman.md
151. network.md
152. https.md
153. encryption.md
154. certificate.md
155. lvalue.md
156. rvalue.md
157. earth.md
158. relation.md
159. lgbt.md
160. good.md
161. c.md
162. people.md
163. turing.md
164. buddha.md
165. babbage.md
166. torvalds.md
167. jesus.md
168. hitler.md
169. einstein.md
170. rms.md
171. marx.md
172. rust.md
173. chess.md
174. set.md
175. branchless.md
176. elon_musk.md
177. woman.md
178. dithering.md
179. tesla.md
180. matrix.md
181. nat.md
182. internet.md
183. regex.md
184. woman.md
185. rust.md
186. capitalism.md
187. usa.md
188. c.md
189. gnu.md
190. postfix.md
191. demultiplexer.md
192. multiplexer.md
193. optical_fiber.md
194. ellipse.md
195. distance.md
196. turing_tarpit.md
197. esolang.md
198. doom.md
199. doom.md
200. cpu.md
201. cache.md
202. spiral.md
203. chess.md
204. trolling.md
205. c.md
206. cpp.md
207. java.md
208. javascript.md
209. python.md
210. lisp.md
211. forth.md
212. brainfuck.md
213. fortran.md
214. pascal.md
215. haskell.md
216. prolog.md
217. smalltalk.md
218. comun.md
219. capitalism.md
220. earth.md
221. gpl.md
222. mit.md
223. cc0.md
224. vim.md
225. emacs.md
226. acme.md
227. debian.md
228. openbsd.md
229. freedos.md
230. haiku.md
231. minix.md
232. gnu.md
233. hurd.md
234. unix.md
235. neural_net.md
236. cross_product.md
237. dot_product.md
238. stack_overflow.md
239. recursion.md
240. compression.md
241. nigger.md
242. censorship.md
243. faggot.md
244. network.md
245. shader.md
246. cos.md
247. shader.md
248. digital_signature.md
249. man_in_the_middle.md
250. coc.md
251. corporation.md
252. oop.md
253. capitalist_software.md
254. c.md
255. github.md
256. fibonacci.md
257. quine.md
258. deep_blue.md
259. bit_field.md
260. integral.md
261. aliasing.md
262. antialiasing.md
263. circular_buffer.md
264. turing_complete.md
265. programming_language.md
266. esolang.md
267. earth.md
268. bazaar.md
269. dot_product.md
270. cross_product.md
271. float.md
272. automorphism.md
273. chess.md
274. encyclopedia.md
275. productivity_cult.md