Discussion between Simon André Forsberg and toto2 - 2014-10-19

last day (15 days later) »

4:45 PM

1

A: Min triangle path - bottom-up

It looks like a good dynamic programming solution. Small Details I don't like that you copy the full triangle in TriangleResult. You can just store the relevant path. You could define rowIndex right before its use in findShortestPath. I don't like raw arrays, but it might OK here for performa...

Simon André Forsberg

From what I can see of my code, I am definitely not using recursion. Where did you get that from? I am using iteration. Your Scala code is not very useful to me at the moment as I have not yet learned Scala (I would like to though).

Your Scala code might fit better in a new question, and a link to it from here, instead of as an answer to this question.

You are not using recursion. What I meant is that your while-loop is equivalent to calling a recursive function. When I read your code I thought it would be cleaner as a recursive function, but that is very arguable. I did not add the section about recursion to say that I disagree with your answer, but just as a suggestion/discussion.

Simon André Forsberg

Sorry, from your answer I thought you said my code was recursive. I misunderstood. The fact that it can cause a Stack Overflow in Java is one reason for why I decided to not make it recursive. What are the types that you would add? Just Row and Solution? The Solution might be a good idea.

It is not very useful at the moment to post Scala code on codereview since there are so few Scala programmers (at least on this site). I did get one useful review at some point however.

Yes, just Solution. I think it can make the recursive solution a lot cleaner. The recursive function takes in the current row and the List[Solution] for the rows below and returns a new List[Solution].

Simon André Forsberg

unfortunately your Scala code is at the moment not very useful for me either as I don't understand much of it. Although it has given me one more reason to learn Scala.

4:45 PM

In Scala, Row is just a "type alias" which makes the code a bit clearer.

Simon André Forsberg

Scala has type aliases? I do like that!

It would be very helpful if you could explain your Scala code a bit. You don't need to, but it would help me learn Scala a lot.

Sorry, I had trouble login to chat.stackexchange.com.

By the way, I don't know if it was clear, but I did it in Scala because that would have taken 2 or 3 pages of code in Java.

Simon André Forsberg

@toto2 Been there. Just a guess: Are you using a Mac?

No. But it said something about "local storage" not being accepted by my browser.

I the end, it's just that I was clicking on the wrong link to log in.

Simon André Forsberg

@toto2 We'll see about that when I understand more about what you were doing ;) Java 8 did make it possible to shorten code quite a lot.

@toto2 happens to all of us.

4:54 PM

True. But it limited compared to Scala. For example, it does not have zip which I used.

The early version of Java 8 had zip, but they removed for some reason...

zip takes List[A] and List[B] and returns List[(A, B)].

(A, B) is a "tuple", or a pair.

Simon André Forsberg

Ah, OK. Java 8 didn't introduce tuples unfortunately. That might be why.

yes...

The main reason why Scala is much shorter is "case classes".

case class Solution(cost: Int, path: List[Int])

Simon André Forsberg

yeah I was just about to ask WTF that is

In Java, you would have to write a class with two member variables, getters, equals, hashCode, toString, constructors. But with that one line, all those things are done automatically. Just saved one page right there!

val sol = Solution(3, List(3))

sol.cost

sol.toString

Those just work from the line case class Solution(cost: Int, path: List[Int])

Simon André Forsberg

so it's a bit like value-types? (not fully like C# and other languages, but... a bit...)

5:00 PM

It's a class, but with much shorter syntax to define it.

Not sure what you mean by value type.

Did you figure function definitions:

def solveOneRow(row: Row, belowSolutions: List[Solution]): List[Solution]

The variable and type are inverted relative to Java. The return type of the function is at the end.

Simon André Forsberg

msdn.microsoft.com/en-us/library/s1ax56ch.aspx - that's Value-types as it is in C#. As I said though, not quite value-types. You'd still need to use .equals and stuff of course, but... yeah, I get what it does in Scala.

require(row.size == belowSolutions.size - 1) is just shorthand to throw an IllegalArgumentException

Simon André Forsberg

@toto2 I haven't got that far yet, but I understand the syntax of that method declaration, yes.

@toto2 I've used ActionScript 3 and Delphi, where the syntax is a bit similar to that so I understand it.

I am stuck at this though:

def addHead(headCost: Int) = Solution(headCost + cost, headCost :: path)

element :: list

is list prepend. In Scala, by default the lists are LinkedList (immutable).

if we had Solution(3, List(3)), then addHead(4) gives:

Solution(7, List(4, 3))

Simon André Forsberg

aha. You might not know this, but... is that similar to how Haskell can use the :: operator?

5:06 PM

Solution is immutable, so adding returns a new Solution.

Yes, all functions languages are similar

Linked lists are always used because they are immutable

I meant: all "functional" languages

Simon André Forsberg

Good, then I just learned one more thing about Haskell at the same time.

I want to learn Haskell too

I read that Scala is the gateway drug to Haskell.

val leftRightSolutions = belowSolutions.zip(belowSolutions.tail)

Simon André Forsberg

@toto2 I did try out the basics of it a while ago:

11

Q: Calculating Luhn-algorithm checksum digit

Today I decided to learn some basic Haskell, and for starters I made a program for calculating the checksum of a Swedish personal identification number. It uses the Luhn-algorithm, aka. IBM MOD-10. Explanation of this code can be found on Swedish Wikipedia and English Wikipedia Here's a descrip...

beginner haskell validation

I'm building pairs of next elements.

You are further along on Haskell than I am.

But the logic in functional languages is similar and I think I am getting the hang of it.

if belowSolutions = [1, 2, 3, 4]

Simon André Forsberg

@toto2 I think I've forgotten more than half of it already though.

5:09 PM

then val leftRightSolutions = belowSolutions.zip(belowSolutions.tail)

= [(1, 2), (2, 3), (3, 4)]

It's like spoken language: if you don't use it, you lose it quickly.

Simon André Forsberg

So leftRightSolutions is a List<Tuple<Integer, Integer>> (so to speak) ?

yes.

Next line uses map.

[1, 2, 3].map(i => i * 10)

gives [10, 20, 30]

That is like Java Stream.

Simon André Forsberg

yeah, that I am familiar with

val minBelowSolutions = leftRightSolutions.map { case (left, right) => if (left.cost < right.cost) left else right }

Simon André Forsberg

isn't case (left, right) => if (left.cost < right.cost) left else right just like Math.min(left, right) ?

5:13 PM

I'm taking the List[(Int, Int)] and getting the mininum of the tow -> List[Int]

yest

I mean "yes".

and "two", not "tow"

Simon André Forsberg

why not use Math.min then? Or is that not possible?

Hint: Up-key to edit previous messages.

I did not know how to use it on a tuple.

But my guess is that I could have done better here.

Yes.

Simon André Forsberg

Hmm... ah, yes, you are comparing by x.cost but returning the actual x.

row.zip(minBelowSolutions).map { case (cost, belowSolution) => belowSolution.addHead(cost) }

zipping List[Int] (costs) with their associated solution

Gives List[(Int, Solution)]

then mapping

using the function addHead we talked about previously to add an element to a Solution

Simon André Forsberg

Alright

5:17 PM

So the function solveOneRow, took in a Row and List[Solution] below and built the new solution.

It's the main recursive method.

Just 3 lines, if you forget the argument checking.

Simon André Forsberg

and val invertedTriangle = triangle.rows.reverse flips the triangle upside-down

yes

val bottomSolutions = invertedTriangle.head.map(cost => Solution(cost, List(cost)))

Simon André Forsberg

creates a solution for each of the bottom elements

builds the initial "solution" for the bottom Row.

It is needed for recursion.

val finalSolution = invertedTriangle.tail.foldLeft(bottomSolutions)((belowSolutions, row) => solveOneRow(row, belowSolutions))

That is a beast.

Simon André Forsberg

that one I have no clue about what it does.

5:20 PM

But I guess Java Stream does have fold too? let me check.

Simon André Forsberg

I believe folding is related to Stream's collect method

No, it actually reduce.

But maybe you are right.

Simon André Forsberg

ah, yes. That's the one I was looking for right now.

Probably the same thing can be done with collect

Simon André Forsberg

reduce is more accurate I think.

5:22 PM

first: [1, 2, 3].tail gives [2, 3]

Simon André Forsberg

yeah, I think so. reduce is probably easier in this case though

(and [1, 2, 3].head gives 1)

Simon André Forsberg

aha, that's similar to Haskell I think

I'm sure Haskell has foldLeft in some way.

Simon André Forsberg

what's the difference between foldLeft and foldRight? (if it exists at all)

5:23 PM

By the way, foldLeft does not have problems with stackoverflow because the Scala compiler actually rewrites it as a while-loop.

But foldRight are for problems where it is impossible to rewrite as a while-loop, and in that case Scala can also get stackoverflow.

[1, 2, 3].foldLeft(0)( (accum, i) => i + accum)

Simon André Forsberg

@toto2 that would return 6 I assume?

No wait...

That is sum using foldLeft. The accum is the "accumulator"; that value is recomputed and propagated each time a new element is processed.

yes, 6

Simon André Forsberg

ok

The first (0), is the initial value of the accum.

in foldLeft(0)(...)

[1, 2, 3].foldRight(List())((i, accumList) => i :: accumList)

This reverses a list.

It cannot be done with foldLeft, but only foldRight.

There is no way you could transform this to a while-loop.

Simon André Forsberg

so trying to write it with foldLeft would produce a compiler Error?

5:29 PM

wait...

Simon André Forsberg

while (!list.isEmpty()) {
    nextElement = list.remove(0);
    newList.add(nextElement);
}

wouldn't that be possible?

or does that not count?

I might be wrong here...

But there are some recursive functions (fold is basically a recursive function) that cannot be transformed to a while-loop.

Simon André Forsberg

ok

A recursive function that can be transformed to a while loop is called "tail recursive".

That means that the recursive function calls itself at the very end only.

It's a bit more subtle, but you can probably find the exact rules on when a recursive function can be transformed to a while-loop.

Simon André Forsberg

I've heard about tail recursion. I believe even JVM can optimize that at some occations.

5:33 PM

No. I don't think so.

Scala does detect tail recursion and does the while-loop transformation, but Java does not.

Simon André Forsberg

I have to ask rolfl about that, I think he mentioned it some time... or perhaps it's only other compilers.

It would be very new if it is the case, but I really don't think so.

val finalSolution = invertedTriangle.tail.foldLeft(bottomSolutions)((belowSolutions, row) => solveOneRow(row, belowSolutions))

Simon André Forsberg

in The 2nd Monitor, 17 secs ago, by rolfl

No, it cannot.

I've mixed it up with some other language.

OK.

I guess you can understand the finalSolution computation.

Note that I call invertedTriangle.tail because I used the bottom row already to compute bottomSolutions and I dont' want to iterate over it again.

Simon André Forsberg

@toto2 I'm not entirely sure about that one yet, but I think I can figure it out.

5:37 PM

It just the main loop. It's your while-loop.

Simon André Forsberg

ok

foldLeft iterates over all Rows, starting at the bottom.

Simon André Forsberg

And then you just return something by writing that statement at the end... (oh how I love explicit return statements...)

finalSolution.head

Simon André Forsberg

@toto2 2nd from bottom technically, no?

5:38 PM

finalSolution is a List[Solution], but I know the top of the pyramid is size 1.

list.head is same as list.get(0)

Yes, 2nd from bottom.

I'm not sure if I could have done something more clever to really start at the bottom.

I guess we covered the whole program.

I just realized that case class Triangle(rows: List[Row])

could also just have been type aliasing: type Triangle = List[Row].

Simon André Forsberg

Alright

thanks

I think I understand it a bit better now.

You really have to put in some effort to really get functional programming.

Simon André Forsberg

There are some Scala reviewers around btw, especially Donald.McLean and amon prefer Scala a lot.

You could learn the syntax and just write Scala as you would Java, but it's not the point.

Do you know about Coursera.

They have a "Functional Programming with Scala" class.

Simon André Forsberg

Yeah, I guess so. I've been wondering how on earth a complex server for an online-game would be written in a functional language.

5:44 PM

It's more about functional programming than just Scala.

Simon André Forsberg

I've heard about Coursera

It's free.

It's taught by Martin Odersky (creator of Scala).

Simon André Forsberg

I'm not a big fan of taking classes anymore though, it often feels like I know too much already.

creator of Scala? Well that's a plus...

That class was really interesting.

As I said, functional programming is a whole different way on thinking.

Whatever you think you know does not really apply in functional programming.

Looked at your Haskell post.

They refer to tail recursion, and also pattern matching, which Scala also does.

Simon André Forsberg

@toto2 yeah I noticed that when I tried out Haskell...

almost as different way of thinking as when I made FizzBuzz in Brainfuck...

5:51 PM

Looked at BrainFuck on widipedia.

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.‌------.--------.>>+.>++.

is the hello world program.

Simon André Forsberg

28

Q: FizzBuzz in Brainfuck

Inspired a bit by a previous Brainfuck question and the recent fizzbuzz invasion, I decided to make FizzBuzz in Brainfuck. The code is entirely my own, except for the inclusion of the Printing a number algorithm that I found on StackOverflow. My code is divided into several parts. Setup Const...

fizzbuzz brainfuck

++++++++++[>++++++++++<-]>>++++++++++>->>>>>>>>>>>>>>>>-->+++++++[->++
++++++++<]>[->+>+>+>+<<<<]+++>>+++>>>++++++++[-<++++<++++<++++>>>]++++
+[-<++++<++++>>]>>-->++++++[->+++++++++++<]>[->+>+>+>+<<<<]+++++>>+>++
++++>++++++>++++++++[-<++++<++++<++++>>>]++++++[-<+++<+++<+++>>>]>>-->
---+[-<+]-<[+[->+]-<<->>>+>[-]++[-->++]-->+++[---++[--<++]---->>-<+>[+
+++[----<++++]--[>]++[-->++]--<]>++[--+[-<+]->>[-]+++++[---->++++]-->[
->+<]>>[.>]++[-->++]]-->+++]---+[-<+]->>-[+>>>+[-<+]->>>++++++++++<<[-
>+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]>>[-]>>>++++++++++<[->-[>+>>]>[+[-<+>]>

is FizzBuzz

I'm impressed.

How long did it take you? How much debugging?

Simon André Forsberg

took me about 8 hours to code, once I had figured out what approach I was going to take. A lot of debugging.

probably the craziest code I have ever written

it was an interesting experience though. I really had to think completely differently than from normal coding.

It's a raw Turing machine?

Simon André Forsberg

not exactly. It's possible to make an almost-Turing machine though. It doesn't have any real 'state' except for the value of the tape that it is currently pointing at. And its tape is not infinite.

It doesn't know where it's pointing either, it just know what value it is pointing at.

So "go to beginning of tape" is quite hard to do. But I solved that by making a special mark on the beginning of tape.

so I'm doing a lot of "go backwards until you reach the value 255"

last day (15 days later) »

Transcript for

Oct '1419

Discussion between Simon André Forsbe…

Imported from a comment discussion on codereview.stackexchange...

algorithm interview-questions java rags-to-riches

join this room
about this room

00:00

06:00

12:00

18:00

all times are UTC

site design / logo © 2024 Stack Exchange Inc; legal

mobile