[Community Puzzle] 1D Spreadsheet


#21

I think it’s a great idea and you ought to push it through.

A few thoughts:

  • You didn’t tell us specifically how you implemented your dependency tracking. This is likely to be crucial to your current blocking point of number of file descriptors.
  • Is systemd available on the CG platform? That would be a very fun way to implement a solution.
  • I’m pretty sure make is available, that could be another not-as-concurrent-but-still-fun way to go.

You piqued my interest; I’m going to have to try it out too. :smiley:


#22

thank you for the encouragement.

i ended up solving it using a makefile (thank you for the hint). it feels a bit cheaty. all my script does is transform the input to a makefile. the makefile does the “heavy lifting” of solving the dependency graph. then again, letting parallel processes sort it out by blocking fifos basically means the linux kernel is solving the dependancy graph.

still, using a makefile feels right too because i am using “the right tool for the job”. because one of the main purpose of a makefile is to sort the dependancy graph.

but the parallel processing with syncing and locking in a bash script had some nerd cred feeling to it. oh well. i guess using a makefile has nerd cred too because all the script kidies today do not even know what a makefile is when all they use is npm.

for your question about my implementation: i suspect that the limit i am hitting is not the file descriptor limit.

here is a rought sketch of my parallel process implementation:

a process roughly does the following:

  1. parse operand and arguments
  2. if both arguments are available then calculate and exit. this is the trivial case.
  3. if an argument is missing then notify the other process (by placing a file) so it knows that this one is waiting. then read from a fifo which will block (until someone writes to the fifo).
  4. if the other process is done it will write to the fifo which will allow this process to continue.
  5. if this process is done collecting all arguments and calculating it will itself see whether some other process is waiting and write to their fifo to allow them to continue.

the use of a file descriptor is when reading and writing to the fifo. also when locking critical sections using flock. critical sections are in point 3 and 5 above (race condition between checking for value and writing value).

no file description action happens simultaneously in a given process. so the extra file descriptor usage of a process is at most one at any point in time. at least as far as i understand. i am by far no expert in linux kernel internals.

one thing i tried was to close stdin and stdout and stderr since i didn’t use them (other than debug print). no effect on the amount of processes i was able to start before error. so i suspected it was not a file descriptor limit.

the error message: /tmp/Answer.sh: fork: retry: Resource temporarily unavailable

a quick search came up with a handfull of internet posts saying it is a file descriptor limit. but it seems that it could be any other limit from ulimit. i did not make a lot of effort to try to understand what limit exactly that i hit.

i tried to optimize a bit here and there but it seemed clear to me that no amount of optimizing will reduce the amount of resources that i need other than solving the dependancy graph before starting the processes. at which point the parallel processes are no longer doing anything cool.

i am curious whether you will be able to solve it using parallel processing in bash. i hope i did not spoil to much for you.

thank you again for encouragement. i am happy that my idea and my rambling about my mourning inspired someone.


#23

Hello everyone,

I submitted a python3 code for this puzzle and it solved all test cases beside the “accounting is hard 1” (92% of the puzzle). I have been looking through and can’t really think of how to debug it. Is there a way so my code can be visible / testable by the community so you could point me in the right direction to what I did wrong?

If this is not the right place for this type of question, please feel free to redirect me and I will follow your indications.

Thank you in advance for your help.
Halogen.


#24

I am wondering if anyone could pass the last test case with C++ implementation.


#25

did you end up using recursion? I tried it but it times out. I’m really out of ideas here. ( using C) ( got up to 10 test case)


#26

@OverCoder Of course, you can pass anything with C++.
@AbsoluteUnit Consider adding memoization (keep the computed cell values to avoid recomputing them several times) to your recursive implementation.


#27

@Niako Thank you! Memoization worked for me.


#28

Thank you very much!! That idea helped me solve last test!


#29

Memoization worked for me too, thank you!


#30

The last Test seems to be impossible to pass with Rust even with Memoization (caching the computed values of referenced cells)
I get a time out on the last test


#31

I did the puzzle in rust and my version is still working. Maybe there is still a huge bottleneck in your code ?
I’m a little bit busy right now, but if you still don’t find the problem you could send me your code.


#32

Way to hard for the easy section, Shadows Of The Knight EP1 for example was much easier, nonetheless it’s in the medium section.


#33

Hmm, so the solution that I’m working with right now in Go is able to solve all but 2 of the test cases (Accounting is hard 1 and Accounting is hard 2)…

“Accounting is hard 1” shows:

Found: “81”
Expected: “-119”

“Accounting is hard 2” shows:

Found: “0”
Expected: “-8526”

I’m wondering if the way that i’m resolving the dependency chains is causing some kind of order of operations issue. Does anyone know if this is a caveat that needs to be considered?


#34

Seriously I’m the first one to publish a solution?
lol

Anyway for those who are stuck here some tips:

create a table / array with 4 dimensions and use it wisely
when you resolve a cell find the initial “VALUES” and cache “on the way back”.
look if you have a cached value first :wink:


#35

Thank you very much!


#36

Hello, mates. I am trying to solve a puzzle in Javascript, but catch error "RangeError: Maximum call stack size exceeded". I have 76% score(can’t pass the last 3 tests). I am creating matrix and cash ‘row’ solutions by pushing them into the end of the row. Pls, help:roll_eyes:


#37

using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

/**

  • Auto-generated code below aims at helping you parse

  • the standard input according to the problem statement.
    **/
    class Solution {
    static void Main(string[] args) {
    int N = int.Parse(Console.ReadLine());
    List < LstClass > lst = new List < LstClass > ();
    long d = 0;
    for (int i = 0; i < N; i++) {
    string[] inputs = Console.ReadLine().Split(’ ');

    string operation = inputs[0];
    string arg1 = inputs[1];
    string arg2 = inputs[2];

    LstClass lc = new LstClass();

    lc.position = i;
    lc.operation = operation;
    lc.arg1 = arg1;
    lc.arg2 = arg2;
    if (operation != “VALUE” && long.TryParse(arg1, out d) && long.TryParse(arg2, out d)) {
    lc.value = lc.FunOperation(operation, long.Parse(arg1), long.Parse(arg2));
    } else if (operation == “VALUE” && long.TryParse(arg1, out d)) {
    lc.value = long.Parse(arg1);
    }
    // Console.WriteLine(“Hi”);
    lst.Add(lc);

}

while (N != lst.Where(x => x.value != null).Count()) {
foreach(LstClass lc in lst.Where(x => x.value == null).ToList()) //should ==null
{

long a1 = 0;
long a2 = 0;

if (!long.TryParse(lc.arg1, out a1)) {
 a1 = long.Parse(lc.arg1.Replace('$', ' '));

 if (lst.Where(x => x.position == a1).Select(x => x.value).First() == null) {
  // Console.WriteLine("Continue1");
  continue;
 } else {
  a1 = (long) lst.Where(x => x.position == a1).Select(x => x.value).First();
 }

}
if (!long.TryParse(lc.arg2, out a2)) {

 if (lc.arg2 == "_") {
  continue;
 }
 a2 = long.Parse(lc.arg2.Replace('$', ' '));

 if (lst.Where(x => x.position == a2).Select(x => x.value).First() == null) {
  //  Console.WriteLine("Continue2");
  continue;
 } else {
  a2 = (long)(lst.Where(x => x.position == a2).Select(x => x.value).First());
 }

}

lc.value = lc.FunOperation(lc.operation, a1, a2);

}
}
// Console.WriteLine(lst.Where(x=>x.value==null).Count());

foreach(LstClass lc in lst) {

Console.WriteLine(lc.value);
}

// for (int i = 0; i < N; i++)
// {

// Write an action using Console.WriteLine()
// To debug: Console.Error.WriteLine(“Debug messages…”);

// Console.WriteLine(“1”);
//}
}

class LstClass {
public long position;
public string operation;
public string arg1;
public string arg2;
public long ? value;

/*
public LstClass()
{
this.value=null;
}
*/

public long FunOperation(string op, long arg1, long arg2) {
long result = 0;
if (op == “ADD”) {
result = arg1 + arg2;
} else if (op == “MULT”) {
result = arg1 * arg2;
} else if (op == “SUB”) {
result = arg1 - arg2;
}
return result;
}

}

}

Can anyone help me on optimization ? Test case 11 and 12 fail due to lack of optimization


#38

I think , I did the similar way but with List

class classname
{
public long position;
public string operation;
public string arg1;
public string arg2;
public long? value;

}
I also posted my code Testcases “Accounting Hard1” and "Accounting Hard2 " fail. Please help


#39

how in the world is this classified as easy? haha I’m burning my brains here XD. I don’t care about code efficiency anymore XD.


#40

I’ve finally racked my brain for less than 48 hours only to make it work on everything, but not on “Accounting is hard 1 & 2” testcases…