Project Euler Language Challenge Blog

As was suggested, I made a blog for my continued work on the Project Euler Language Challenge, with an introduction, a table of my progress, and my first additional problem solved.

http://pelangchallenge.blogspot.com/

[MMc] Random Ship Designs

The jam is long over (and I lost!), but I'm having a good time following through with the random spaceship generator for Starlight 2:

Congratulations to Sam, Dan, and Mike, who all clearly scoped their impressive projects well and won the jam!

[Sam] Victory

With 4 minutes to spare, I reached my goal of 20 project Euler problems in different languages in 24 hours. I learned a lot of languages, some real, some not so real - but overall this was very fun, and I may try to extend this challenge to more (esoteric) language over longer stretches of time.

[Dan] Rasterizer Hindsights

so here at the end i have found some interesting issues things out about my rasterizer.

[MMc] Multiple ships

Multiple ships in Starlight 2, with detail views shown in popup windows.  30 minutes until the deadline.

[MMc] Modules and hexification implemented

Starlight2 can now properly construct a legal (but stupid) random ship from an image. Now it is time to interact with other ships, initially in combat. The time alotted for this is specifically 75 minutes, since the jam ends at 3pm today.

A Randomly-Constructed Ship

1. Build GUI infrastructure for popup ship windows (equivalent to the main view in a traditional RTS)
1. Window render
2. Window draw
3. Window resize
4. Window close
5. Zoom control
2. Ship View inside the popup windows
1. Draw ships (with zoom and pan)
2. Show modules as plain hexagons
3. Right-mouse pans view inside of a window
4. Render module icons
5. Find the module under a mouse
3. Draw main view that shows a "realistic" universe (equivalent to a minimap in a traditional RTS)
1. Integrate starfield prototype
2. Overlay GUI
3. Show ships
4. Show free modules
5. Draw paths
4. Main view interaction
1. Zoom control
2. Right mouse pans
3. Support selection of ships
4. Provide waypoint GUI
5. Warp-drive
5. Modules & interaction
1. Make hexification symmetric
2. Drag within ship
3. Drag outside ship
4. Drag inside ship
5. Click to activate module
6. Target modules in other ships
6. Simulation
1. Compute dynamic commodities, e.g., heat, power, etc.
2. Simulate attacks
3. Trading (needs more GUI)
7. Polish graphics
1. Starfield background pan and zoom
2. Per-user color
3. GUI stylization: bloom, noise, ripple on hit
4. Re-coloring of ships
5. Clip module view to the actual window bounds
8. Polish UI
1. Clip the mouse to the window when panning, or hide the mouse and allow it to go outside

[Michael] Victory!

After a sleep that did not last long enough, I quickly refactored my code to compute and store only the form factors for a single patch at a time (which requires O(n) space as opposed to the old O(n^2)). This slows down computation, since we have to recompute form factors every bounce, but makes large scenes able to not take over my entire hard drive.

I then spent some time fixing bugs and debugging scenes. Note to everyone: Dabrovic Sponza has pretty awful tesselation, don't use it at all possible. But anyway, I changed one of the doors in Dabrovic Sponza to emit lots of light and let my radiosity solver run on a course tesselation for a few dozen seconds (it did direct + some of the first bounce indirect in that time frame), giving me:

I'm going to try on Crytek Sponza; then profile and do the easiest optimizations possible before 3. But I ran radiosity on Sponza and had a soft lighting image in <1 minute; so I win!

[Sam] Steady Progress

7 left, with 4 languages I really know left.
One lesson I have learned in the recent problems: I used up J far too early.
Anyway, now I am more so in "learn cool/interesting/reasonable language" mode than the "do crazy things" mode, on account of time...but Shakespeare and INTERCAL are still in my mind for future use if I get my 20 done.

Problem 11: PHP

Find the largest product of 4 adjacent numbers in a 20x20 grid

This wasn't too bad, other than PHP being hard to debug and me forgetting to put $'s on array indices.

https://dl.dropboxusercontent.com/u/34972177/PELC/e11.php

Problem 12: Go

Find the value of the first Triangle number with > 500 divisors

This language was, for once, fun to work with

https://dl.dropboxusercontent.com/u/34972177/PELC/e12.go

Problem 13: Common Lisp

Find the first 10 digit of the sum of 50 large integers

This was trivial in Common Lisp, though it could be hard in other languages...so I went with the trivial solution.

https://dl.dropboxusercontent.com/u/34972177/PELC/e13.lisp

[MMc] Module Design

I've been working on the programmatic design for the elements of the ship. Modules consist of up to seven hexagonal Features, themselves arranged in a hexagonal shape. Features have no variable state beyond their identification (i.e., they are enumerated values). Modules are randomly instantiated into the universe and are indivisible once instantiated. They can be damaged and torn/ejected/blasted from ships (and repaired), but can't be fragmented.

A module generates a mask for itself that is used for rendering borders and other effects. Because modules are rendered in computer-display style, it is appropriate that damaged modules use the mask to render "television static" noise patterns over themselves, as if the signal were breaking down.

Features are represented by icons.  There is a generic, useless Feature (let's call it CORRIDOR) that dilutes the value of a Module.  Some compound Features, such as ARMORED_THRUSTER, disproportionally enhance the value of the Module containing them.

Weapons can only target border tiles in a ship, so there is an advantage to packing them tightly and using armor on the periphery (this is intentionally analogous to walls in RTS games).

Some features have area effects, such as SHIELD and CLOAK generators.  One must use multiple instances to cover a large ship.

It is raining quite hard. Several motorists do not understand correct etiquite/legally required maneuvers at crosswalks, such as pausing their headlong rush to a damp collision-induced grave long enough to admit a pedestrian to cross, much less not drenching said pedestrian as they hurtle past unminding and, quite likely, unconscious in any higher-order neural sense. Nonetheless, I reached lab without (new) physical injury.

[MMc] Panning and Zooming

Pan and zoom work on the world map and in ship windows.  I had to add some extra hooks to G3D to support processing mouse events directly on a GuiWindow.  Usually we process events on GuiControls instead, so this case had never occured before.

1. Build GUI infrastructure for popup ship windows (equivalent to the main view in a traditional RTS)
1. Window render
2. Window draw
3. Window resize
4. Window close
5. Zoom control
2. Ship View inside the popup windows
1. Draw ships (with zoom and pan)
2. Show modules as plain hexagons
3. Right-mouse pans view inside of a window
4. Find the module under a mouse
5. Draw module icons
3. Draw main view that shows a "realistic" universe (equivalent to a minimap in a traditional RTS)
1. Integrate starfield prototype
2. Overlay GUI
3. Show ships
4. Show free modules
5. Draw paths
4. Main view interaction
1. Zoom control
2. Right mouse pans
3. Support selection of ships
4. Provide waypoint GUI
5. Warp-drive
5. Modules & interaction
1. Make hexification symmetric
2. Drag within ship
3. Drag outside ship
4. Drag inside ship
5. Click to activate module
6. Target modules in other ships
6. Simulation
1. Compute dynamic commodities, e.g., heat, power, etc.
2. Simulate attacks
3. Trading (needs more GUI)
7. Polish graphics
1. Starfield background pan and zoom
2. Per-user color
3. GUI stylization: bloom, noise, ripple on hit
4. Re-coloring of ships
5. Clip module view to the actual window bounds
8. Polish UI
1. Clip the mouse to the window when panning, or hide the mouse and allow it to go outside

[Michael] Radiosity!

I modified G3D so that it supports vertex colors throughout the system, and by default uses them to add to the ambient light.

Then I made a mapping from vertices to their adjacent patches, and every time I iterate on radiosity I replace the color at a given vertex with a simple average.

Lots left to do, not the least of which is checking the radiometry. But first I'll continually run it while moving the light source to get a nice video, but then I need to modify the algorithm to allow me to load Sponza. Right now I'm taking the easy way out and computing the form factors for all pairs of patches in advance. This is n^2, so on scenes with a million triangles, this takes 4 TB of space... If I switch to only storing all the form factors for one patch at a time I can reign this in to be reasonable.

I'll start again after I wake up. Good night!

so i took a little break but have gotten back to work. I have got the basic lambertian shading finished and have done a good deal of optimizations to decrease the time within the inner loop. After profiling i can say that the greatest amount of time is being used to make up for my sloppy way of making sure that my rasterizer can render from any camera position. I pretty much just translate everything into the cameras space at each step. As the render is now it cannot truly render cornell box in real time but is not to far off. Here is a video, while it may seem that it is rendering really fast, that is just the magic of the g3d recorder that takes the video and makes it 30 frames a second.

I will probably work a little bit longer tonight and then get some sleep and get ready for a hard day of coding tomorrow in my attempt to reach real-time. If i fix up the sloppy coordinate conversions and add a better algorithm to determine pixel coverage i should be able to achieve real time. 

Problems 7-10

Some more problems done...now my problems aren't dealing with ridiculous languages, its dealing with the whiplash from changing languages so quickly and getting confused on basic syntax for that reason, and more mundane issues...such as using floor instead of ceiling in my solution for #10, which let one perfect square slip into a list of all primes < 2000000.

Problem 7: Racket/Scheme

What is the 10001st Prime Number?

https://dl.dropboxusercontent.com/u/34972177/PELC/e7.rkt

Problem 8: Eyes

What is the largest product of 5 consecutive integers in <list of integers>

This one was trivially easy just by looking at it...not sure whether this one meets my "20" goal or not, as no programming was necessary

Problem 9: Javascript

What is the product abc of the unique pythagorean triple such that a + b + c = 1000?

https://dl.dropboxusercontent.com/u/34972177/PELC/e9.html

Problem 10: ML

What is the sum of all prime numbers < 2000000?

https://dl.dropboxusercontent.com/u/34972177/PELC/e10.sml

[Michael] Radiosity Update

So I spent the morning and a portion of the afternoon reading different sources on radiosity and implementing a new feature in G3D: automatic subdivision of triangles until a threshold edge length is met by all edges. See it here on the Cornell Box with a threshold of  0.45 meters (all edges are less than that).

The next thing I worked on was the "form factor" part of the radiosity algorithm (described here). It basically describes the fraction of energy that leaves one patch of surface and arrives at another, given that the energy scatters diffusely. I treat each triangle in the scene as a patch, and compute form factors between all patches. I then multiply the form factor by the visibility function (which I treat as 1 or 0 for now, depending on whether the center of the patches are visible from each other. To get more accurate results, I can either subdivide the triangles more or implement a stochastic approximation of visibility.

Anyway, I can visualize the form factors for any given patch. I diplay the patch values as GL_POINTS in the center of the patch. The red dot is the center of the patch I am currently visualizing the form factors for, and the other dots represent the magnitude of the form factor for the other patches paired with the selected patch. Brighter means higher form factors.

Note the values aren't purely form factors, I also combine with visibility before display: see how the back left is all black where the tall box blocks the line-of-sight to the red patch.

Finally, I actually implemented radiosity... I chose a progressive variant that evaluates a bounce at a time.

Here's a gif of 0-3 bounce illumination using this technique (displayed in the same way as the form factors... as GL_POINTS at the center of the patches).

You can see it starts out with almost everything black (besides a few patches in the top at the emitter, which are hard to see over the bloom of the direct light). The first bounce is direct illumination, and illuminates most areas (though not those in direct shadow. After the next bounce, you can start to see color bleeding on the sides of the boxes.

Next up: pushing the radiosity values out to vertices and doing a full render.

[MMc] Basic Graphics Complete

We broke for pizza and then reconvened to hack some more.  My iPod died--it had been playing for 12 hours straight! Here's the current rendering of Starlight2:

Ships in the starfield and popup GUI windows for inspecting them

The hexification isn't properly centered, but first I want to take on getting panning working correctly on the ship and main views to help with debugging. My task list, with completed items in green, is below.

1. Build GUI infrastructure for popup ship windows (equivalent to the main view in a traditional RTS)
1. Window render
2. Window draw
3. Window resize
4. Window close
5. Zoom control
2. Ship View inside the popup windows
1. Draw ships (with zoom and pan)
2. Show modules as plain hexagons
3. Left mouse selects, drags, and activates module
4. Right-mouse pans view inside of a window
5. Icon modules
3. Draw main view that shows a "realistic" universe (equivalent to a minimap in a traditional RTS)
1. Integrate starfield prototype
2. Overlay GUI
3. Show ships
4. Show free modules
5. Draw paths
4. Main view interaction
1. Support zooming
2. Support selection of ships
3. Provide waypoint GUI
4. Warp-drive
5. Module interaction
1. Drag within ship
2. Drag outside ship
3. Drag inside ship
4. Activate
5. Target modules in other ships
6. Simulation
1. Compute dynamic commodities, e.g., heat, power, etc.
2. Simulate attacks
3. Trading (needs more GUI)
7. Polish graphics
1. Per-user color
2. GUI stylization: bloom, noise, ripple on hit
3. Re-coloring of ships

Problems 4-6

3 more problems down...one was in Ruby, which was easy/fun enough, one in Whenever, which is a ridiculous language except for when it is easy to write a solution in one line, and one is in Ook, a variant of Brainfuck. Despite how fun it has been to write brainfuck code, if I actually want to reach my goal, I am going to have to stick with more "reasonable" languages for a bit

Problem 4: Ruby

Find the largest palindrome which is the product of 2 3-digit numbers

https://dl.dropboxusercontent.com/u/34972177/PELC/e4.rb

Problem 5: Whenever

Find the smallest natural number divisible by the integers 1,...,20

https://dl.dropboxusercontent.com/u/34972177/PELC/e5.we

Problem 6: Ook! (Compiled to Ook! from Brainfuck)

Find the difference between (1 + 2 + ... + 100)^2 and (1^2 + 2^2 + ... + 100^2)

https://dl.dropboxusercontent.com/u/34972177/PELC/e6.bf

https://dl.dropboxusercontent.com/u/34972177/PELC/e6.ook

[MMc] GUI Built

Here's the plan, updated with the implemented portion in green.  Current rendering of the game:

Resizable, Skinned Windows and GUI Controls over a dynamic Starfield

1. Build GUI infrastructure for popup ship windows (equivalent to the main view in a traditional RTS)
1. Window render
2. Window draw
3. Window resize
4. Window close
5. Zoom control
2. Ship View inside the popup windows
1. Draw ships (with zoom and pan)
2. Show modules as plain hexagons
3. Left mouse selects, drags, and activates module
4. Right-mouse pans view inside of a window
5. Icon modules
3. Draw main view that shows a "realistic" universe (equivalent to a minimap in a traditional RTS)
1. Integrate starfield prototype
2. Overlay GUI
3. Show ships
4. Show free modules
5. Draw paths
4. Main view interaction
1. Support zooming
2. Show ships
3. Support selection of ships
4. Provide waypoint GUI
5. Warp-drive
5. Module interaction
1. Drag within ship
2. Drag outside ship
3. Drag inside ship
4. Activate
5. Target modules in other ships
6. Simulation
1. Compute dynamic commodities, e.g., heat, power, etc.
2. Simulate attacks
3. Trading (needs more GUI)
7. Polish graphics
1. Per-user color
2. GUI stylization: bloom, noise, ripple on hit
3. Re-coloring of ships

So after some work i have a functioning rasterizer that will render a simple scene like Cornell Box pretty fast. I was originally running into a but where i did not properly convert the points to camera space before projecting them onto the camera plane. This caused a weird error which looked like this.

After i fixed the issue it looks like this. The change in brightness is not from my render but from a change in the scene.

The shading might look pretty bad right now but that is because i am not focusing on it. What I want to do now is optimize the hell out of the rasterizer and then at the end I will deal with trying to make the shading look nice. right now it is just a simple lambertian.

View from the Graphics Lab: 24 hours to go

Sam

Mike

Morgan and Dan

[Sam] 3 Solutions

Problem 1: BrainFuck

Find the sum of all multiples of 3 or 5 less than 1000: (Answer printed in unary)

The code I actually wrote:
https://dl.dropboxusercontent.com/u/34972177/PELC/e1.bf

The more cool-looking version:
https://dl.dropboxusercontent.com/u/34972177/PELC/e1Unreadable.bf

Problem 2: Haskell

Find the sum of all even Fibonacci numbers less than 4000000

https://dl.dropboxusercontent.com/u/34972177/PELC/e2.hs

Problem 3: J

Find the largest prime factor of 600851475143 (First line is my initial solution, the second a better one James helped me find)

https://dl.dropboxusercontent.com/u/34972177/PELC/e3.jis

[Sam] One down...

Because of the difficulty of using it, I decided that problem number 1 should be written in BrainF. It took most of the morning, but I have succeeded at this task. I unfortunately needed to compromise my rule of "programs must output the solution, not an intermediary value needed to compute it", but because the intermediary value was extremely easy to parse into a solution (I output a number of characters equal to the solution), but it would have been incredibly difficult to actually print a number, I decided to stick with the intermediary version. My next problem will be done using a much more sane language...maybe something like Haskell, which I have never used, though it is a language that is actually meant to be used.

edit: I did not compromise my rules, the number is printed in unary.

[Michael] Radiosity

I want a short project that won't feature creep on me as much as my games always do, given our reduced time and my lack of prep time.

I'm going to use OptiX and G3D to write one or more radiosity solvers; hopefully getting results in real time.

Victory condition: Having a standalone G3D program that can basically render

 in a minute.

Bonus condition 0: Reduce render time to 1-2 seconds
Bonus condition 1: Reduce render time to 67 ms
Bonus condition 2: Support dynamic objects.

[Dan] Rasterizer

My plan for this hackathon is to write a software rasterizer that will hopefully by the end of the forty eight hours be able to render some cool scenes in real time.

[Sam] Project Euler Language Challenge

I don't have any good ideas for games/etc. floating around in my head right now (though the Dominion AI idea proposed over lunch today sounds interesting...that may or may not happen at some later date). So, I am deciding to pick up a proposal that came up over an earlier lunch during the year that sounded like it would be fun - try to solve as many Project Euler problems as possible (in 48 hours), but each solution must be written in a different language. My goal for now is to do at least 20, though I can hope for more.

Goals:

• Have fun revisiting Project Euler problems / potentially solving new ones for me
• Learn the basics of some "real" programming languages that I have never gotten a chance to use (like Haskell, Perl, Ruby...)
• Muck around with silly / ridiculous programming languages while having an actual goal in mind for their use instead of playing with them just to play with them.

In order to make specific what I will be doing, I have established a set of rules to formalize my task:

Rules:

• Each "solution" must both follow the Project Euler rule of taking about a minute or less to run to completion, and in addition must actually be capable of outputting the solution in some manner - a program that gives information that can then be used to deduce the solution through additional work or guess and check over a small range is not sufficient.
• Two languages, in order to be considered "different," must not be related by age or have a subset relation in code. For example, Java 1.5, Java 1.6, and Java 1.7 will all be considered "Java," even though each is a slightly different language. Also, C/C++ will be considered the same language as any Project Euler C++ code will probably use very few, if any features that are not in the C subset. In addition, for the purpose of this challenge, "assembly" and "machine code" will be considered one language - I am not going to just go around and write assembly for a bunch of different architectures.
• A "language" is defined loosely as basically anything you can write in in order to instruct a computer to perform a sequence of instructions - languages need not be Turing complete or live up to any other such qualifications. Meta-languages such as the C Preprocessor and the C++ template meta-language will be considered unique languages, though preference will generally be given to "real" languages before working with them.
• I will say that non-programming solutions are invalid - among these would be pencil and paper, calculator usage, graph plotting, excel spreadsheets, etc - due to the increased difficulty in establishing an adequate metric for difference among such methods, and due to not being in the spirit of this challenge. However, this rule may change at a later date, as trying to solve problems in this way could be pretty fun.
• Programs must be either hand-written or programatically written by programs I wrote - a solution is not in "Java Bytecode" because I used the Java compiler, but a solution could be in Whitespace if I wrote a Python script that allowed me to convert semi-human-readable text into Whitespace.
• A new Project Euler account will be made for this project in order to record my progress
• Outside Project-Euler specific help is not allowed, including but not limited to looking at the forums for a problem and looking at my own older solutions (most of which are written in Scheme/Racket, Python, or Java)
• I will post my solutions to the Project Euler forums for each problem as I complete them

[MMc] Starlight

For the hackathon I'm revisiting a game that I wrote in a month two years ago but never released because the original version became too large to maintain.

Title: Starlight
Platform: Windows
Players: 1 (maybe)
Concept: An RTS where your "empire" is a spaceship that you can fly. Add new rooms, upgrade the hull, trade and battle with other ships.

Related Games:  Galaxy Trucker, Minecraft, FTL, The Ur Quan Masters, Age of Empires, tower defense and RTS games

Technology Plan: 

• Use G3D, 3DS Max, Photoshop, SVN, Audacity, CFXR
• Spaceships are made from hex tiles, with math from my codeheart.js example
• Minimize state and assets, e.g., 
• Procedural generation of the galaxy and visual elements
• Dervive all ship data directly from an single image of the ship
• Rely heavily on emergence

Art Plan: 

• Procedural starfield for tactical and navigation view
• Ships are sprites pre-rendered in 3DS Max from TurboSquid models
• UI is drawn in monochrome and then noised and bloomed, using tech developed on A Thousand Moonlit Seas

Design Plan:

• Straight RTS mechanics, except components are found and bought instead of built directly to avoid players having to learn a tech tree and recipies
• No "units"
• Emphasis should be on building and configuring the ship, with flying, combat, trading, etc. forming increasingly tighter reward cycles.
• AI is (as always) a risk.  Multiplayer?

Early Asset Tests:

Procedural Starfield

Spaceship Rendered in 3DS Max

Spaceship Hexified on Load

Screenshots of Old Prototypes:

Fully 3D Prototype Emphasizing Flying

Another 3D Prototype

2.5D Minecraft-like Prototype with Intricate Wiring Mechanics

2.5D Prototype with UI

Combat in the 2.5D Prototype

Machinis Ludo 4: Algorithm Jam

The Williams graphics group will run a two-day graphics hackathon to celebrate the end of summer research internships. Others are welcome to join us, but based on the short notice we're not going to do a full game jam and explicitly invite people.

Proposal Deadline: Monday 2013-08-05.  Projects can be solo or group, and need not be a game. This is a great chance to design a new G3D feature, implement a graphics algorithm that you've always been curious about, or just play with a demo effect (e.g., maybe in shadertoy).  If you want to make a game, that's of course welcome--I'm currently planning to make a game myself.

Start: 2013-08-08 9:00am ET (early starts and exploration are fine)
End:  2013-08-09 3:00pm ET...for real this time, so that we can have a cool-down party.

Desert Morning shadertoy sample

Sleeping and showering at some point in during the hackathon period is highly encouraged.  We'll have a mix of takeout and meals out in the lab--sometimes taking a walk for coffee, or half hour at the pizza place is better for workflow than plowing through and eating at your desk.

As usual, post your proposal to the blog before the deadline and then post regularly during the hackathon to document our progress.